Problem Statement

You are given a sequence A=(A_1,\ldots,A_N) of length N. You perform the following operation exactly once.

• Choose a pair of integers (L,R) such that 1\leq L \leq R \leq N. Replace each of A_L,A_{L+1},\ldots,A_R with A_L.

How many different sequences are possible as A after the operation?

Constraints

• All input values are integers.
• 1 \leq N \leq 10^6
• 1\leq A_i \leq N

Sample Input 1

4
1 1 2 3

Sample Output 1

4

The possible sequences after the operation are the following four sequences:

• (1,1,1,1)
• (1,1,1,3)
• (1,1,2,2)
• (1,1,2,3)

For example, (1,1,1,3) can be obtained by performing the operation with L=2,R=3.

Sample Input 2

10
2 5 6 5 2 1 7 9 7 2

Sample Output 2

41

Problem Statement

N slimes are arranged in a line. The size of the i-th slime from the left is P_i, and its color is C_i. Here, the sizes of the slimes are distinct.

A sequence of slimes is called a good sequence when it satisfies the following condition:

• By repeatedly performing the operation of swapping the positions of two adjacent slimes of different colors, it is possible to arrange the slimes in ascending order of size.

To make the sequence of slimes a good sequence, you can perform the following operation any number of times (possibly zero):

• Choose a slime, and change the color of the slime to any integer between 1 and N, inclusive. This operation costs x, where x is the color of the slime immediately before this operation.

Find the minimum total cost required to make the sequence of slimes a good sequence.

Constraints

• All input values are integers.
• 1 \leq N \leq 2\times 10^5
• 1\leq P_i \leq N
• 1\leq C_i \leq N
• P is a permutation of (1,\ldots,N).

Sample Input 1

4
3 1 2 4
1 2 1 3

Sample Output 1

1

Change the color of the 3-rd slime to 2. Then, by swapping the 1-st and 2-nd slimes, and swapping the 2-nd and 3-rd slimes, it is possible to arrange the slimes in ascending order of size, making it a good sequence.

The required cost is 1, since the color of the 3-rd slime immediately before the operation was 1.

Sample Input 2

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

Sample Output 2

28

Problem Statement

A sequence B=(B_1,\ldots,B_N) of length N consisting of integers between 1 and N (inclusive) is called a good sequence if and only if it satisfies the following condition:

• For every interval [l,r]\ (1\leq l \leq r \leq N), there exists an integer x\ (l\leq x\leq r) such that the following condition holds:
  • Prepare a graph with N vertices numbered from 1 to N and zero edges. For each l \leq i \leq r, if i\neq x, add an edge between vertices i and B_i. Then, vertices l, l+1,\ldots,r form a tree. That is, vertices l, l+1,\ldots,r are connected.

You are given a sequence A=(A_1,\ldots,A_N) where each element is either an integer between 1 and N, or -1. Find the number, modulo 998244353, of ways to replace the elements that are -1 in A with integers between 1 and N such that A becomes a good sequence.

Constraints

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

Sample Input 1

3
-1 -1 -1

Sample Output 1

7

The replacements that satisfy the condition are the following seven:

• (1,1,2)
• (2,1,2)
• (2,2,2)
• (2,3,1)
• (2,3,2)
• (2,3,3)
• (3,1,2)

For example, in the case of A=(1,1,2), that the interval [1,2] satisfies the condition can be confirmed by setting x=1, where vertices 2 and A_2=1 are connected and vertices 1,2 form a tree.

Similarly, intervals [1,1],[2,2],[3,3],[2,3],[1,3] also satisfy the condition, so (1,1,2) is a good sequence.

Sample Input 2

3
-1 3 -1

Sample Output 2

3

The replacements that satisfy the condition are the following three:

• (2,3,1)
• (2,3,2)
• (2,3,3)

Sample Input 3

6
2 3 -1 -1 -1 -1

Sample Output 3

21

Problem Statement

Among the elements of a permutation P=(P_1,\ldots,P_N) of (1,\ldots,N), those that satisfy the following condition are called good elements:

• The element can be included in both a longest increasing subsequence and a longest decreasing subsequence of P.

You are given integers N and K. Determine whether there exists a permutation P of (1,\ldots,N) such that there are exactly K good elements, and if it exists, find one.

Answer for T test cases.

Constraints

• All input values are integers
• 1 \leq T \leq 2\times 10^5
• 1 \leq N \leq 2\times 10^5
• 0\leq K \leq N
• The sum of N over all test cases does not exceed 2\times 10^5.

Sample Input 1

3
1 0
7 2
2 1

Sample Output 1

-1
7 4 6 2 3 1 5
-1

In the 2-nd test case, P_4=2 and P_5=3 are good elements.

Indeed, (2,3,5) is a longest increasing subsequence of P. Also, (7,6,2,1) and (7, 6, 3, 1) are longest decreasing subsequences of P.

Therefore, in this sample output, 2 and 3 are good elements. The other elements are not good elements, so this output satisfies the condition.

In the 1-st and 3-rd test cases, there does not exist a permutation satisfying the condition. Thus, output -1.

Problem Statement

There is an N\times N board, where N is at least 4. The cells on the outermost edge of the board that are not corners are called good cells. More formally, among (i,j) such that 1\leq i,j \leq N and i=1 or i=N or j=1 or j=N, the cells excluding (1,1),(1,N),(N,1),(N,N) are called good cells. Here, (r,c) refers to the cell in row r and column c.

All good cells have integers written on them. This information is given as four integer sequences of length N-2: U=(U_1,\ldots,U_{N-2}),D=(D_1,\ldots,D_{N-2}),L=(L_1,\ldots,L_{N-2}),R=(R_1,\ldots,R_{N-2}).

Each element of these integer sequences corresponds to the integer written on a good cell as follows:

• U_i: (1,i+1)
• D_i: (N,i+1)
• L_i: (i+1,1)
• R_i: (i+1,N)

Also, all cells on the board are initially colored white. You can perform the following operation any number of times:

• Choose two good cells that have never been chosen in any previous operation. Let the two chosen good cells be (r_1,c_1) and (r_2,c_2). For all (i,j) satisfying \min(r_1,r_2)\leq i \leq \max(r_1,r_2) and \min(c_1,c_2)\leq j \leq \max(c_1,c_2), color (i,j) black. The cost of the operation is the sum of the integers written on the two chosen good cells.

Find the minimum total cost required to color all cells black.

Answer for T test cases.

Constraints

• All input values are integers.
• 1 \leq T \leq 12500
• 4 \leq N \leq 5\times 10^4
• 0\leq U_i,D_i,L_i,R_i \leq 10^9
• The sum of N over all test cases does not exceed 5\times 10^4.

Sample Input 1

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

Sample Output 1

36
15
21

In the 1-st test case, you can color all cells black as follows:

• Perform the operation choosing (1,2) and (3,4).
• Perform the operation choosing (2,4) and (4,2).
• Perform the operation choosing (4,3) and (2,1).
• Perform the operation choosing (3,1) and (1,3).

The total cost is (1+4)+(3+5)+(6+7)+(8+2)=36.

For the 2-nd and 3-rd test cases, the input boards are illustrated below: