Problem Description

There are $ N $ candies, and the deliciousness of the $ i $ -th candy is $ A_i $.

Define $ f(l,r) $ $(1 \leq l \leq r \leq N)$ as the maximum sum of the deliciousness of the candies eaten from the $ l $ -th to the $ r $ -th under the following condition:

Condition: You cannot eat two consecutive candies. That is, for all $ i $ satisfying $l \leq i < r$, you cannot eat both the $ i $ -th and $ i+1 $ -th candies.

Given the deliciousness of each candy, create a program that calculates the sum of $ f(l,r) $ for all pairs $ (l,r) $ satisfying $1 \leq l \leq r \leq N$, modulo $ 998,244,353 $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $\cdots$ $ A_N $

Output Format

Output the sum of $ f(l,r) $ for all pairs $ (l,r) $ satisfying $1 \leq l \leq r \leq N$, modulo $ 998,244,353 $, in one line to the standard output.

Sample Input and Output

Sample Input #1

3
1 2 3

Sample Output #1

15

Sample Input #2

4
1 100 100 1

Sample Output #2

805

Sample Input #3

1
1000000000

Sample Output #3

1755647

Sample Input #4

10
850534838 749655434 745817507 991867417 645519349 373697182 427765279 182404140 260664174 366393413

Sample Output #4

554337161

Notes/Hints

Constraints

• $1 \leq N \leq 200,000$.
• $1 \leq A_i \leq 1,000,000,000$ $(1 \leq i \leq N)$.

Subtasks

1. ($ 10 $ points) $N \leq 300$.
2. ($ 20 $ points) $A_i \leq 300$ $(1 \leq i \leq N)$.
3. ($ 70 $ points) No additional constraints.

Sample Explanation 1

For $ l=2, r=3 $, you cannot eat both the 2nd and 3rd candies, so the optimal choice is to eat only the 3rd candy, making $ f(l,r)=3 $. For $ l=1, r=3 $, the optimal choice is to eat the 1st and 3rd candies, making $ f(l,r)=1+3=4 $. The value to output is $ f(1,1)+f(1,2)+f(1,3)+f(2,2)+f(2,3)+f(3,3)=1+2+4+2+3+3=15 $.

Sample Explanation 3

Output the result modulo $ 998,244,353 $.

见题面 Input 部分

见题面 Output 部分