Problem Statement

You are given a sequence of N positive integers: A=(A_1,A_2,\dots,A_N).

You will repeat the following operation until the length of A becomes 1.

• Let k be the length of A before this operation. Choose integers i and j such that \max(\{A_1,A_2,\dots,A_{k}\})=A_i,\min(\{A_1,A_2,\dots,A_{k}\})=A_j, and i \neq j. Then, replace A_i with (A_i \bmod A_j). If A_i becomes 0 at this moment, delete A_i from A.

Find the number of operations that you will perform. We can prove that, no matter how you choose i,j in the operations, the total number of operations does not change.

Constraints

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

Sample Input 1

3
2 3 6

Sample Output 1

3

You will perform 3 operations as follows:

• Choose i=3,j=1. You get A_3=0, and delete A_3 from A. Now you have A=(2,3).
• Choose i=2,j=1. You get A_2=1. Now you have A=(2,1).
• Choose i=1,j=2. You get A_1=0, and delete A_1 from A. Now you have A=(1), and terminate the process because the length of A becomes 1.

Sample Input 2

6
1232 452 23491 34099 57341 21488

Sample Output 2

12

Problem Statement

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

You can repeat the following two kinds of operations in any order to make P sorted in increasing order.

• Operation A: Choose an integer i such that 1 \leq i \leq N-1, and swap P_i and P_{i+1}.

• Operation B: Choose an integer i such that 1 \leq i \leq N-2, and swap P_i and P_{i+2}.

Find a sequence of operations with the following property:

• The number of Operations A is the minimum possible.

• The total number of operations is not larger than 10^5.

Under the Constraints of this problem, we can prove that a solution always exists.

Constraints

• 2 \leq N \leq 400
• 1 \leq P_i \leq N \,(1 \leq i \leq N)
• P_i \neq P_j \,(1 \leq i < j \leq N)
• All values in input are integers.

Sample Input 1

4
3 2 4 1

Sample Output 1

4
A 3
B 1
B 2
B 2

In this Sample Output, P changes like this: (3,2,4,1) \rightarrow (3,2,1,4) \rightarrow (1,2,3,4) \rightarrow (1,4,3,2) \rightarrow (1,2,3,4).

Note that you don't have to minimize the total number of operations.

Sample Input 2

3
1 2 3

Sample Output 2

0

Sample Input 3

6
2 1 4 3 6 5

Sample Output 3

3
A 1
A 3
A 5

Problem Statement

N people, numbered 1,2,\ldots ,N, are going to stand on the number line. Let's denote by x_i the coordinate the Person i stands at. Then, x_i should be an integer satisfying L_i \leq x_i \leq R_i. Multiple people can occupy the same coordinate.

We define the dissatisfaction level as the following formula:

\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}|x_j-x_i|

Find the minimum possible value of the dissatisfaction level.

Constraints

• 2 \leq N \leq 3 \times 10^5
• 1 \leq L_i \leq R_i \leq 10^7 \,(1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

3
1 3
2 4
5 6

Sample Output 1

4

If we let x_1=3,x_2=4,x_3=5, we get the dissatisfaction level of 4. We cannot make it 3 or less, so the answer is 4.

Sample Input 2

3
1 1
1 1
1 1

Sample Output 2

0

Sample Input 3

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

Sample Output 3

15

Problem Statement

Consider a sequence of integer sets of length N: S=(S_1,S_2,\dots,S_N). We call a sequence brilliant if it satisfies all of the following conditions:

• S_i is a (possibly empty) integer set, and its elements are in the range [1,M]. (1 \le i \le N)

• The number of integers that is included in exactly one of S_i and S_{i+1} is 1. (1 \le i \le N-1)

We define the score of a brilliant sequence S as \displaystyle \prod_{i=1}^{M} ( the number of sets among S_1,S_2,\dots,S_N that include i.).

Find, modulo 998244353, the sum of the scores of all possible brilliant sequences.

Constraints

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

Sample Input 1

2 3

Sample Output 1

24

Among all possible brilliant sequences, the following 6 have positive scores.

• S_1=\{1,2\},S_2=\{1,2,3\}
• S_1=\{1,3\},S_2=\{1,2,3\}
• S_1=\{2,3\},S_2=\{1,2,3\}
• S_1=\{1,2,3\},S_2=\{1,2\}
• S_1=\{1,2,3\},S_2=\{1,3\}
• S_1=\{1,2,3\},S_2=\{2,3\}

All of them have a score of 4, so the sum of them is 24.

Sample Input 2

12 34

Sample Output 2

786334067

Problem Statement

N students, numbered 1,2,\ldots,N, took an examination. Student i\,(1 \leq i \leq N) had to score at least B_i points to graduate, where they actually scored A_i points.

You can repeat the following operation any number of times (possibly zero):

• Choose two students, and swap their scores.

Your goal is to make everyone graduate. Determine whether it is possible. If it is possible, find the maximum number of students whose scores do not change during the process.

Constraints

• 2 \leq N \leq 3 \times 10^5
• 1 \leq A_i,B_i \leq 10^9\,(1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

3
1 2
3 1
3 3

Sample Output 1

1

If you swap scores of Student 1 and 2, everyone can graduate. Here, the number of students whose scores do not change is 1 (only Student 3).

Sample Input 2

2
100 1
100 1

Sample Output 2

2

Sample Input 3

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

Sample Output 3

-1

Sample Input 4

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

Sample Output 4

3

Problem Statement

Consider strings of length N consisting of A, B, and C. Among them, find the number of strings that satisfy the following condition, modulo 2:

• Let S_i be the string formed by the first i characters of S. Also let A_i, B_i, and C_i be the numbers of A's, B's, and C's in S_i, respectively. For all i such that 1 \le i \le N, the following holds:
  • A_i-B_i \le X
  • B_i-C_i \le Y
  • C_i-A_i \le Z

You have T test cases to solve.

Constraints

• 1 \le T \le 10
• 1 \le N \le 10^9
• 0 \le X,Y,Z \le 10^9
• All values in input are integers.

Sample Input 1

1
3 2 1 0

Sample Output 1

0

8 strings satisfy the condition: AAB,AAC,ABA,ABC,ACA,ACB,BAA,BAC. Therefore the answer is 0.

Sample Input 2

10
1 22 9 92
14 7 74 39
23 50 8 6
93 40 9 60
68 8 47 64
11 68 18 24
3 26 54 8
46 17 90 86
86 76 45 55
80 68 79 62

Sample Output 2

1
0
0
0
1
1
1
0
1
0