Problem Statement

You are given a permutation P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N).

You want to satisfy P_i=i for all i=1,2,\dots,N by performing the following operation zero or more times:

• Choose an integer k such that 1 \leq k \leq N. If k \geq 2, sort the 1-st through (k-1)-th terms of P in ascending order. Then, if k \leq N-1, sort the (k+1)-th through N-th terms of P in ascending order.

It can be proved that under the constraints of this problem, it is possible to satisfy P_i=i for all i=1,2,\dots,N with a finite number of operations for any P. Find the minimum number of operations required.

You have T test cases to solve.

Constraints

• 1 \leq T \leq 10^5
• 3 \leq N \leq 2 \times 10^5
• P is a permutation of (1,2,\dots,N).
• All input values are integers.
• The sum of N across the test cases in a single input is at most 2 \times 10^5.

Sample Input 1

3
5
2 1 3 5 4
3
1 2 3
7
3 2 1 7 5 6 4

Sample Output 1

1
0
2

For the first test case,

• Performing the operation with k=1 results in P becoming (2,1,3,4,5).

• Performing the operation with k=2 results in P becoming (2,1,3,4,5).

• Performing the operation with k=3 results in P becoming (1,2,3,4,5).

• Performing the operation with k=4 results in P becoming (1,2,3,5,4).

• Performing the operation with k=5 results in P becoming (1,2,3,5,4).

Specifically, performing the operation with k=3 results in P satisfying P_i=i for all i=1,2,\dots,5. Therefore, the minimum number of operations required is 1.

For the third test case, performing the operation with k=4 followed by k=3 results in P changing as (3,2,1,7,5,6,4) \rightarrow (1,2,3,7,4,5,6) \rightarrow (1,2,3,4,5,6,7).

Problem Statement

For strings S and T consisting of lowercase English letters, and a string X consisting of 0 and 1, define the string f(S,T,X) consisting of lowercase English letters as follows:

• Starting with an empty string, for each i=1,2,\dots,|X|, append S to the end if the i-th character of X is 0, and append T to the end if it is 1.

You are given a string S consisting of lowercase English letters, and strings X and Y consisting of 0 and 1.

Determine if there exists a string T (which can be empty) such that f(S,T,X)=f(S,T,Y).

You have t test cases to solve.

Constraints

• 1 \leq t \leq 5 \times 10^5
• 1 \leq |S| \leq 5\times 10^5
• 1 \leq |X|,|Y| \leq 5\times 10^5
• S is a string consisting of lowercase English letters.
• X and Y are strings consisting of 0 and 1.
• The sum of |S| across all test cases in a single input is at most 5 \times 10^5.
• The sum of |X| across all test cases in a single input is at most 5 \times 10^5.
• The sum of |Y| across all test cases in a single input is at most 5 \times 10^5.

Sample Input 1

3
araara
01
111
araaaa
100100
0010111
abacabac
0
1111

Sample Output 1

Yes
No
No

Below, string concatenation is represented using +.

For the 1st test case, if T=ara, then f(S,T,X)=S+T=araaraara and f(S,T,Y)=T+T+T=araaraara, so f(S,T,X)=f(S,T,Y).

For the 2nd and 3rd test cases, there is no T that satisfies the condition.

Sample Input 2

2
empty
10101
00
empty
11111
111

Sample Output 2

Yes
Yes

T can be empty.

Problem Statement

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

Write one of the characters 0 and 1 in each cell of an N-by-N grid so that all of the following conditions are satisfied:

• Let S_i be the string obtained by concatenating the characters in the i-th row from the 1-st to the N-th column. Then, S_{P_1} < S_{P_2} < \dots < S_{P_N} in lexicographical order.
• Let T_i be the string obtained by concatenating the characters in the i-th column from the 1-st to the N-th row. Then, T_{Q_1} < T_{Q_2} < \dots < T_{Q_N} in lexicographical order.

It can be proved that for any P and Q, there is at least one way to write the characters that satisfies all the conditions.

Constraints

• 2 \leq N \leq 500
• P and Q are permutations of (1,2,\dots,N).
• All input values are integers.

Sample Input 1

3
1 2 3
2 1 3

Sample Output 1

001
101
110

In this sample, S_1=001, S_2=101, S_3=110, and T_1=011, T_2=001, T_3=110. Therefore, S_1 < S_2 < S_3 and T_2 < T_1 < T_3 hold, satisfying the conditions.

Sample Input 2

15
8 15 10 2 4 3 1 13 5 12 9 6 14 11 7
4 1 5 14 3 12 13 7 11 8 6 2 9 15 10

Sample Output 2

010001111110101
001000000101001
010001001100010
010000011110010
010011101101101
100101110100000
111100011001000
000001001100000
100011011000101
000111101011110
101010101010101
011010101011110
010011000010011
100110010110101
000101101100100

Problem Statement

You are given a permutation P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N).

Consider the following operations k\ (k=2,3,\dots,N) on this permutation.

• Operation k: For i=1,2,\dots,k-1 in this order, if P_i > P_{i+1}, swap the values of the i-th and (i+1)-th elements of P.

You are also given a non-decreasing sequence A=(A_1,A_2,\dots,A_M)\ (2 \leq A_i \leq N) of length M.

For each i=1,2,\dots,M, find the inversion number of P after applying the operations A_1, A_2, \dots, A_i in this order.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 2 \leq A_i \leq N
• P is a permutation of (1,2,\dots,N).
• A_i \leq A_{i+1} for i=1,2,\dots,M-1.
• All input values are integers.

Sample Input 1

6
3 2 4 1 6 5
2
4 6

Sample Output 1

3
1

First, operation 4 is performed. During this, P changes as follows: (3,2,4,1,6,5) \rightarrow (2,3,4,1,6,5) \rightarrow (2,3,4,1,6,5) \rightarrow (2,3,1,4,6,5). The inversion number of P afterward is 3.

Next, operation 6 is performed, where P eventually becomes (2,1,3,4,5,6), whose inversion number is 1.

Sample Input 2

20
12 14 16 8 7 15 19 6 18 5 13 9 10 17 4 1 11 20 2 3
15
3 4 6 8 8 9 10 12 13 15 18 18 19 19 20

Sample Output 2

117
116
113
110
108
105
103
99
94
87
79
72
65
58
51

Problem Statement

An undirected graph with numbered vertices is called a good graph if it has a spanning tree T that satisfies the following condition. Here, an edge connecting two vertices u and v (u < v) is denoted as edge (u,v).

• For every edge (u,v) (u < v) in the graph, the minimum and maximum vertex numbers on the unique simple path connecting vertices u and v in T are u and v, respectively.

You are given a simple connected undirected graph G with N vertices numbered from 1 to N. The graph G has M edges, and the i-th edge connects vertices A_i and B_i (A_i < B_i).

For each i=1,2,\dots,M, determine whether the graph obtained by removing the i-th edge from G is a good graph.

Constraints

• 2 \leq N \leq 2 \times 10^5
• N-1 \leq M \leq 2 \times 10^5
• 1 \leq A_i < B_i \leq N
• All input values are integers.
• The given graph is a simple connected undirected graph.

Sample Input 1

6 9
1 3
1 5
2 5
2 6
3 4
3 5
3 6
4 6
5 6

Sample Output 1

No
No
No
No
Yes
No
No
Yes
Yes

Consider the case where edge (4,6) is removed. A spanning tree formed by edges (1,3),(2,5),(3,4),(3,5),(5,6) satisfies the condition. For example, for edge (3,6), the simple path connecting vertices 3 and 6 traverses vertices 3,5,6 in this order, and the minimum and maximum vertex numbers on the path are 3 and 6, respectively, thus satisfying the condition. By verifying the other edges similarly, it can be seen that this spanning tree satisfies the condition, so the answer is Yes.

On the other hand, consider the case where edge (1,5) is removed. The same spanning tree does not satisfy the condition. For edge (4,6), the simple path connecting vertices 4 and 6 traverses vertices 4,3,5,6 in this order, and the minimum and maximum vertex numbers on the path are 3 and 6, respectively, thus not satisfying the condition. It can also be shown that no other spanning tree satisfies the condition, so the answer is No.

Sample Input 2

5 4
1 2
2 3
3 4
4 5

Sample Output 2

No
No
No
No

Removing an edge may disconnect the graph.

Sample Input 3

15 20
12 13
7 8
5 7
8 10
9 12
4 5
11 12
2 4
6 8
4 14
1 2
14 15
2 9
3 8
2 15
10 11
13 14
8 9
7 14
5 13

Sample Output 3

No
No
No
Yes
Yes
No
Yes
No
No
No
No
No
No
No
No
Yes
No
No
No
No

Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N. On this sequence, the following operation can be performed:

• Choose l and r (1\leq l < r \leq N) such that A_l=A_r, A_{l+1}=A_{l+2}=\dots=A_{r-1}, and A_{l+1}\neq A_l. Replace each of A_{l+1},A_{l+2},\dots,A_{r-1} with A_l. The cost of this operation is r-l-1.

You will repeat this operation until there is no l and r (1\leq l < r \leq N) such that A_l=A_r, A_{l+1}=A_{l+2}=\dots=A_{r-1}, and A_{l+1}\neq A_l. Find the minimum total cost of such a series of operations.

Constraints

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

Sample Input 1

7
1 2 3 2 3 2 1

Sample Output 1

7

For example, if you perform the operation with (l,r)=(3,5), (2,6), (1,7) in this order, A changes as follows: (1,2,3,2,3,2,1)\rightarrow (1,2,3,3,3,2,1) \rightarrow (1,2,2,2,2,2,1) \rightarrow (1,1,1,1,1,1,1), after which there is no l and r with the said property. The total cost of this series of operations is 1+3+5=9.

On the other hand, if you perform the operation with (l,r)=(2,4), (4,6), (1,7) in this order, A changes as follows: (1,2,3,2,3,2,1)\rightarrow (1,2,2,2,3,2,1) \rightarrow (1,2,2,2,2,2,1) \rightarrow (1,1,1,1,1,1,1). The total cost of this series of operations is 1+1+5=7.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

0

Sample Input 3

40
1 2 3 4 5 6 7 8 7 6 5 6 7 8 7 6 5 4 3 2 2 1 2 3 4 5 4 5 6 7 8 7 7 6 5 6 6 7 8 8

Sample Output 3

44