Problem Statement

For a sequence a = (a_1, a_2, a_3, \dots, a_k), let f(a) be the sum of its elements after the following is done:

• For each i = 1, 2, 3, \dots, k, in this order, do the following operation:
  add the current maximum value of an element in a to a_i.

You are given a sequence of length N: A = (A_1, A_2, A_3, \dots, A_N).
For each integer k between 1 and N (inclusive), find f(a) when a = (A_1, A_2, A_3, \dots, A_k).

Constraints

• 1 \le N \le 2 \times 10^5
• 1 \le A_i \le 10^7
• All values in input are integers.

Sample Input 1

3
1 2 3

Sample Output 1

2
8
19

For example, when a = (A_1, A_2, A_3), f(a) is computed as follows:

• First, for i = 1, add to a_1 the current maximum value of a, which is 3, making a = (4, 2, 3).
• Next, for i = 2, add to a_2 the current maximum value of a, which is 4, making a = (4, 6, 3).
• Finally, for i = 3, add to a_3 the current maximum value of a, which is 6, making a = (4, 6, 9).
• f(a) is the sum of the elements of a now, which is 19.

Problem Statement

We have a grid with H rows and W columns. Let (i, j) denote the square at the i-th row and j-th column.
You are given H strings S_1, S_2, S_3, \dots, S_H that describe the square, as follows:

• if the j-th character of S_i is R, (i, j) is painted red;
• if the j-th character of S_i is B, (i, j) is painted blue;
• if the j-th character of S_i is ., (i, j) is unpainted.

Let k be the number of unpainted squares. Among the 2^k ways to paint each of those squares red or blue, how many satisfy the following condition?

• The number of red squares visited while getting from (1, 1) to (H, W) by repeatedly moving one square right or down, including (1, 1) and (H, W), is always the same regardless of the path taken.

Since the count may be enormous, print it modulo 998244353.

Constraints

• 2 \le H \le 500
• 2 \le W \le 500
• S_i is a string of length W consisting of R, B, and ..

Sample Input 1

2 2
B.
.R

Sample Output 1

2

There are two ways to get from (1, 1) to (2, 2) by repeatedly moving right or down, as follows:

• (1, 1) \rightarrow (1, 2) \rightarrow (2, 2)
• (1, 1) \rightarrow (2, 1) \rightarrow (2, 2)

If we paint (1, 2) and (2, 1) in different colors, the above two paths will contain different numbers of red squares, violating the condition.
On the other hand, if we paint (1, 2) and (2, 1) in the same color, the two paths will contain the same numbers of red squares, satisfying the condition.
Thus, there are two ways to satisfy the condition.

Sample Input 2

3 3
R.R
BBR
...

Sample Output 2

0

There may be no way to satisfy the condition.

Sample Input 3

2 2
BB
BB

Sample Output 3

1

There is no unpainted square, and the current grid satisfies the condition, so the answer is 1.

Problem Statement

Given are two sequences of length N each: A = (A_1, A_2, A_3, \dots, A_N) and B = (B_1, B_2, B_3, \dots, B_N).
Determine whether it is possible to make A equal B by repeatedly doing the operation below (possibly zero times). If it is possible, find the minimum number of operations required to do so.

• Choose an integer i such that 1 \le i \lt N, and do the following in order:
  • swap A_i and A_{i + 1};
  • add 1 to A_i;
  • subtract 1 from A_{i + 1}.

Constraints

• 2 \le N \le 2 \times 10^5
• 0 \le A_i \le 10^9
• 0 \le B_i \le 10^9
• All values in input are integers.

Sample Input 1

3
3 1 4
6 2 0

Sample Output 1

2

We can match A with B in two operations, as follows:

• First, do the operation with i = 2, making A = (3, 5, 0).
• Next, do the operation with i = 1, making A = (6, 2, 0).

We cannot meet our objective in one or fewer operations.

Sample Input 2

3
1 1 1
1 1 2

Sample Output 2

-1

In this case, it is impossible to match A with B.

Sample Input 3

5
5 4 1 3 2
5 4 1 3 2

Sample Output 3

0

A may equal B before doing any operation.

Sample Input 4

6
8 5 4 7 4 5
10 5 6 7 4 1

Sample Output 4

7

Problem Statement

Let us define balanced parenthesis string as a string satisfying one of the following conditions:

• An empty string.
• A concatenation of s and t in this order, for some non-empty balanced parenthesis strings s and t.
• A concatenation of (, s, ) in this order, for some balanced parenthesis string s.

Also, let us say that the i-th and j-th characters of a parenthesis string s is corresponding to each other when all of the following conditions are satisfied:

• 1 \le i < j \le |s|.
• s_i = (.
• s_j = ).
• The string between the i-th and j-th characters of s, excluding the i-th and j-th characters, is a balanced parenthesis string.

You are given a sequence of length 2N: A = (A_1, A_2, A_3, \dots, A_{2N}).
Let us define the score of a balanced parenthesis string s of length 2N as the sum of |A_i - A_j| over all pairs (i, j) such that the i-th and j-th characters of s are corresponding to each other.

Among the balanced parenthesis strings of length 2N, find one with the maximum score.

Constraints

• 1 \le N \le 2 \times 10^5
• 1 \le A_i \le 10^9
• All values in input are integers.

Sample Input 1

2
1 2 3 4

Sample Output 1

(())

There are two balanced parenthesis strings of length 4: (()) and ()(), with the following scores:

• (()): |1 - 4| + |2 - 3| = 4
• ()(): |1 - 2| + |3 - 4| = 2

Thus, (()) is the only valid answer.

Sample Input 2

2
2 3 2 3

Sample Output 2

()()

(()) and ()() have the following scores:

• (()) : |2 - 3| + |3 - 2| = 2
• ()() : |2 - 3| + |2 - 3| = 2

Thus, either is a valid answer in this case.

Problem Statement

There are N people, Person 1 through Person N, standing on a number line. Person i is now at coordinate A_i on the number line.
Here, A_1 < A_2 < A_3 < \dots < A_N and all A_i are even numbers.

We will now hold a party for k seconds.
During the party, each person can freely move on the number line at a speed of at most 1 per second. (It is also allowed to move in the negative direction within the speed limit.)
The people request that the following condition be satisfied for every integer i such that 1 \le i \lt N:

• there is at least one moment during the party (including the moment it ends) when Person i and Person i + 1 are at the same coordinate.

Find the minimum k for which there is a strategy that the people can take to satisfy all the conditions.
We can prove that the answer is an integer under the Constraints of this problem.

Constraints

• 2 \le N \le 2 \times 10^5
• 0 \le A_i \le 10^9
• A_1 < A_2 < A_3 < \dots < A_N
• A_i is an even number.

Sample Input 1

3
0 6 10

Sample Output 1

5

During the party lasting 5 seconds, each person should move as follows:

• Person 1: always moves in the positive direction at a speed of 1.
• Person 2: moves in the positive direction at a speed of 1 during the first 2 seconds, then in the negative direction at a speed of 1 during the remaining 3 seconds.
• Person 3: always moves in the negative direction at a speed of 1.

If they move in this way, Person 2 and Person 3 will be at the same coordinate exactly 2 seconds after the beginning, and Person 1 and Person 2 will be at the same coordinate at the end of the party.
Thus, they can satisfy all the conditions for k = 5. For smaller k, there is no strategy to satisfy all of them.

Sample Input 2

5
0 2 4 6 8

Sample Output 2

3

During the party lasting 3 seconds, each person should, for example, move as follows:

• Person 1: always moves in the positive direction at a speed of 1.
• Person 2: moves in the positive direction at a speed of 1 during the first 2 seconds, then in the negative direction at a speed of 1 during the remaining 1 second.
• Person 3: does not move at all.
• Person 4: moves in the negative direction at a speed of 1 during the first 2 seconds, then in the positive direction at a speed of 1 during the remaining 1 second.
• Person 5: always moves in the negative direction at a speed of 1.

Sample Input 3

10
0 2 4 6 8 92 94 96 98 100

Sample Output 3

44

Problem Statement

Problems F and F2 have the same Problem Statement but different Constraints and Time Limits.

There are N bottles of wine in Takahashi's cellar, arranged in a row from left to right.
The tastiness of the i-th bottle from the left is A_i.
Aoki will choose K bottles from these N and steal them. However, Takahashi is careful enough to notice the theft if the following condition is satisfied:

• There exist D consecutive bottles such that two or more of them are stolen. (D = 2 in this problem.)

For every way of stealing bottles without getting noticed by Takahashi, find the total tastiness of the bottles stolen, and then find the sum of all those values.
Since the sum can be enormous, print it modulo 998244353.

Constraints

• D = 2
• 2 \le N \le 3 \times 10^5
• 1 \le K \le \left\lceil \frac{N}{D} \right\rceil (\left\lceil x \right\rceil represents the smallest integer not less than x.)
• 1 \le A_i \lt 998244353
• All values in input are integers.

Sample Input 1

4 2 2
1 4 2 3

Sample Output 1

14

The possible ways to steal bottles and the total tastiness for each of them are as follows:

• Steal the 1-st and 3-rd bottles from the left, for the total tastiness of 1 + 2 = 3.
• Steal the 1-st and 4-th bottles from the left, for the total tastiness of 1 + 3 = 4.
• Steal the 2-nd and 4-th bottles from the left, for the total tastiness of 4 + 3 = 7.

Thus, the answer is 3 + 4 + 7 = 14.

Sample Input 2

5 3 2
4 7 5 3 8

Sample Output 2

17

There is no choice but to steal the 1-st, 3-rd, and 5-th bottles.

Sample Input 3

12 4 2
107367523 266126484 149762920 57456082 857431610 400422663 768881284 494753774 152155823 740238343 871191740 450057094

Sample Output 3

136993014

Problem Statement

Problems F and F2 have the same Problem Statement but different Constraints and Time Limits.

There are N bottles of wine in Takahashi's cellar, arranged in a row from left to right.
The tastiness of the i-th bottle from the left is A_i.
Aoki will choose K bottles from these N and steal them. However, Takahashi is careful enough to notice the theft if the following condition is satisfied:

• There exist D consecutive bottles such that two or more of them are stolen.

For every way of stealing bottles without getting noticed by Takahashi, find the total tastiness of the bottles stolen, and then find the sum of all those values.
Since the sum can be enormous, print it modulo 998244353.

Constraints

• 2 \le D \le N \le 10^6
• 1 \le K \le \left\lceil \frac{N}{D} \right\rceil (\left\lceil x \right\rceil represents the smallest integer not less than x.)
• 1 \le A_i \lt 998244353
• All values in input are integers.

Sample Input 1

4 2 2
1 4 2 3

Sample Output 1

14

The possible ways to steal bottles and the total tastiness for each of them are as follows:

• Steal the 1-st and 3-rd bottles from the left, for the total tastiness of 1 + 2 = 3.
• Steal the 1-st and 4-th bottles from the left, for the total tastiness of 1 + 3 = 4.
• Steal the 2-nd and 4-th bottles from the left, for the total tastiness of 4 + 3 = 7.

Thus, the answer is 3 + 4 + 7 = 14.

Sample Input 2

5 2 3
1 5 7 7 3

Sample Output 2

20

The possible ways to steal bottles and the total tastiness for each of them are as follows:

• Steal the 1-st and 4-th bottles from the left, for the total tastiness of 1 + 7 = 8.
• Steal the 1-st and 5-th bottles from the left, for the total tastiness of 1 + 3 = 4.
• Steal the 2-nd and 5-th bottles from the left, for the total tastiness of 5 + 3 = 8.

Sample Input 3

18 4 4
107367523 266126484 149762920 57456082 857431610 400422663 768881284 494753774 152155823 740238343 871191740 450057094 208762450 787961742 90197530 77329823 193815114 707323467

Sample Output 3

228955567