Problem Statement

There is a grid consisting of N cells numbered 1 to N.

Initially, cell i (1 \le i \le N) has an integer i \bmod 2 written in it. You can perform the following operation any number of times, possibly zero:

• Choose cells l and r (l+1 < r) that satisfy the following conditions, and replace each of the integers written in cells l+1, l+2, \dots, r-1 with the integer written in cell l.
  • The integer written in cell l is equal to the integer written in cell r.
  • The integer written in cell i (l < i < r) is different from the integer written in cell l.

Find the number, modulo 998244353, of sequences of operations that result in the integers written in cell i (1 \leq i \leq N) being A_i.

Two sequences of operations are considered different if and only if their lengths are different or there exists a positive integer t not exceeding the length of the sequences such that the (l, r) chosen in the t-th operations differ.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq A_i \leq 1

Sample Input 1

6
1 1 1 1 1 0

Sample Output 1

3

To make the integers written in each cell i equal to A_i, for example, you can perform the following operations. (Here, we represent the state of the grid as a sequence X = (X_1, X_2, \dots, X_N).)

• Initially, X = (1, 0, 1, 0, 1, 0).
• Choose cells 2 and 4. X becomes (1, 0, 0, 0, 1, 0).
• Choose cells 1 and 5. X becomes (1, 1, 1, 1, 1, 0).

Besides the above, there are two other sequences of operations that result in the integers written in cell i being A_i, so the answer is 3.

Sample Input 2

10
1 1 1 1 1 0 1 1 1 0

Sample Output 2

9

Problem Statement

There are N pieces placed on a number line. Initially, all pieces are placed at distinct coordinates.
The initial coordinates of the pieces are X_1, X_2, \ldots, X_N.
Takahashi can repeat the following operation any number of times, possibly zero.

Choose an integer i such that 1 \leq i \leq N-3, and let M be the midpoint between the positions of the i-th and (i+3)-rd pieces in ascending order of coordinate.
Then, move each of the (i+1)-th and (i+2)-th pieces in ascending order of coordinate to positions symmetric to M.
Under the constraints of this problem, it can be proved that all pieces always occupy distinct coordinates, no matter how one repeatedly performs the operation.

His goal is to minimize the sum of the coordinates of the N pieces.
Find the minimum possible sum of the coordinates of the N pieces after repeating the operations.

Constraints

• 4 \leq N \leq 2 \times 10^5
• 0 \leq X_1 < X_2 < \cdots < X_N \leq 10^{12}
• All input values are integers.

Sample Input 1

4
1 5 7 10

Sample Output 1

21

If Takahashi chooses i = 1, the operation is performed as follows:

• The coordinates of the 1st and 4th pieces in ascending order of coordinate are 1 and 10, so the coordinate of M in this operation is (1 + 10)/2 = 5.5.
• The 2nd piece from the left moves from coordinate 5 to 5.5 + (5.5 - 5) = 6.
• The 3rd piece from the left moves from coordinate 7 to 5.5 - (7 - 5.5) = 4.

After this operation, the sum of the coordinates of the four pieces is 1 + 4 + 6 + 10 = 21, which is minimal. Thus, print 21.

Sample Input 2

6
0 1 6 10 14 16

Sample Output 2

41

Problem Statement

There are N boxes. For i = 1, 2, \ldots, N, the i-th box contains A_i red balls and B_i blue balls.

You are also given two permutations P = (P_1, P_2, \ldots, P_N) and Q = (Q_1, Q_2, \ldots, Q_N) of (1, 2, \ldots, N).

Takahashi can repeat the following operation any number of times, possibly zero:

• Choose an integer 1 \leq i \leq N, and take all the balls from the i-th box into his hand.
• Put all the red balls in his hand into the P_i-th box.
• Put all the blue balls in his hand into the Q_i-th box.

His goal is to make a state where all boxes other than the X-th box contain no balls by repeating the above operations. Determine whether it is possible to achieve his goal, and if possible, print the minimum number of operations needed to achieve it.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq A_i, B_i \leq 1
• 1 \leq P_i, Q_i \leq N
• P and Q are permutations of (1, 2, \ldots, N).
• 1 \leq X \leq N
• All input values are integers.

Sample Input 1

5 3
0 1 0 1 0
0 0 1 0 1
4 1 2 3 5
3 4 5 2 1

Sample Output 1

4

The numbers of red and blue balls in each box are A = (0, 1, 0, 1, 0) and B = (0, 0, 1, 0, 1), respectively. Consider the following steps:

• First, perform the operation on the 5th box. As a result, A = (0, 1, 0, 1, 0), B = (1, 0, 1, 0, 0).
• Next, perform the operation on the 2nd box. As a result, A = (1, 0, 0, 1, 0), B = (1, 0, 1, 0, 0).
• Then, perform the operation on the 1st box. As a result, A = (0, 0, 0, 2, 0), B = (0, 0, 2, 0, 0).
• Finally, perform the operation on the 4th box. As a result, A = (0, 0, 2, 0, 0), B = (0, 0, 2, 0, 0).

These four operations achieve a state where all boxes other than the X-th (3rd) box contain no balls. This is the minimum number of operations possible.

Sample Input 2

5 3
0 0 0 0 0
0 0 0 0 0
4 1 2 3 5
3 4 5 2 1

Sample Output 2

0

There are no balls in any boxes. Thus, the state where all boxes other than the X-th (3rd) box contain no balls is already achieved, so the required number of operations is 0.

Sample Input 3

2 2
1 1
1 1
1 2
1 2

Sample Output 3

-1

There is no way to perform the operation to achieve a state where all boxes other than the X-th (2nd) box contain no balls.

Sample Input 4

10 10
0 0 0 0 0 0 1 0 1 0
0 0 0 0 1 1 0 0 1 0
1 4 9 5 8 2 3 6 10 7
7 4 9 10 6 3 1 2 8 5

Sample Output 4

8

Problem Statement

There are N slimes lined up in a row from left to right. For i = 1, 2, \ldots, N, the i-th slime from the left has size A_i.
For each K = 1, 2, \ldots, N, solve the following problem.

Takahashi is the K-th slime from the left in the initial state. Find the maximum size that he can have after performing the following action any number of times, possibly zero:

• Choose a slime adjacent to him that is strictly smaller than him, and absorb it. As a result, the absorbed slime disappears, and Takahashi's size increases by the size of the absorbed slime.

When a slime disappears due to absorption, the gap is immediately closed, and the slimes that were adjacent to the disappearing slime (if they exist) become adjacent (see the explanation in Sample Input 1).

Constraints

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

Sample Input 1

6
4 13 2 3 2 6

Sample Output 1

4 30 2 13 2 13

As an example, consider the problem for K = 4. We will refer to the sizes of the remaining slimes, listed from left to right, with Takahashi's size enclosed in square brackets [ ], as the state of the row. That is, the initial state is (4, 13, 2, [3], 2, 6). Consider the following sequence of actions by Takahashi.

• He absorbs the slime to his right. As a result, the absorbed slime disappears, and his size becomes 3 + 2 = 5. The state becomes (4, 13, 2, [5], 6).
• He absorbs the slime to his left. As a result, the absorbed slime disappears, and his size becomes 5 + 2 = 7. The state becomes (4, 13, [7], 6).
• He absorbs the slime to his right. As a result, the absorbed slime disappears, and his size becomes 7 + 6 = 13. The state becomes (4, 13, [13]).

There are no slimes adjacent to him that are strictly smaller than him, so he cannot perform any more actions. His final size is 13, which is the maximum possible.

Sample Input 2

12
22 25 61 10 21 37 2 14 5 8 6 24

Sample Output 2

22 47 235 10 31 235 2 235 5 235 6 235

Problem Statement

Among the ways to label the edges of a complete graph G with N vertices with positive integers, a graph satisfying the following condition is called a "good complete graph".

• There exists no path that visits all N vertices exactly once and whose sequence of edge labels, in the order the edges are traversed, is non-decreasing.

Determine whether a good complete graph exists. If it exists, construct one that minimizes the maximum label assigned to an edge.

Constraints

• 2 \leq N \leq 20

Sample Input 1

5

Sample Output 1

Yes
2 1 4 4
4 3 1
1 3
2

For example, consider the path that visits vertices in the order 2, 5, 1, 4, 3. The sequence of edge labels traversed is (1, 4, 4, 1), which is not non-decreasing.

Moreover, there is no path whose sequence of edge labels is non-decreasing, so this graph satisfies the condition.

Also, when N=5, it is impossible to assign labels so that the maximum label assigned to an edge is 3 or less, so this output is valid.

Sample Input 2

2

Sample Output 2

No