Problem Statement

You are given a positive integer N.
Output the sum of all integers from 1 to N, that is, 1+2+\cdots+N.

Constraints

• 1 \leq N \leq 100
• N is an integer.

Sample Input 1

5

Sample Output 1

15

Since 1+2+3+4+5=15, output 15.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

29

Sample Output 3

435

Problem Statement

You are given a sequence of positive integers A=(A_1,A_2,\ldots,A_N) of length N.
Find the number of pairs of integers (l,r) satisfying 1\leq l\leq r\leq N that satisfy the following condition:

For every integer i satisfying l\leq i\leq r, A_i is not a divisor of A_l+A_{l+1}+\cdots+A_r.

Constraints

• 1 \leq N \leq 50
• 1 \leq A_i \leq 1000
• All input values are integers.

Sample Input 1

5
8 6 10 5 7

Sample Output 1

6

We have A=(8,6,10,5,7).

For example, (l,r)=(1,2) satisfies the condition because A_l+A_{l+1}+\cdots+A_r=A_1+A_2=14, and neither A_1=8 nor A_2=6 is a divisor of 14.
On the other hand, (l,r)=(1,3) does not satisfy the condition because A_l+A_{l+1}+\cdots+A_r=A_1+A_2+A_3=24, and A_1=8 is a divisor of 24.

The pairs that satisfy the condition are (l,r)=(1,2), (1,4), (2,3), (2,4), (3,5), (4,5), which is six pairs, so output 6.

Sample Input 2

3
1 1 1

Sample Output 2

0

Problem Statement

There are N dominoes standing in a row on a number line. The i-th domino is standing at coordinate i and has height A_i.

When the i-th domino falls to the right, all dominoes in the range between coordinates i and i+A_i-1, inclusive, fall to the right.

How many dominoes will fall in total when the first domino falls to the right?

Constraints

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

Sample Input 1

4
3 1 4 1

Sample Output 1

4

When the first domino falls to the right, the second and third dominoes also fall to the right. When the third domino falls to the right, the fourth domino also falls.

Sample Input 2

9
1 4 1 4 2 1 3 5 6

Sample Output 2

1

When the first domino falls to the right, no other dominoes will fall.

Sample Input 3

10
5 4 3 2 1 1 2 3 4 5

Sample Output 3

5

Problem Statement

You are given a directed graph with N vertices and M edges.
The vertices are numbered from 1 to N, and the i-th edge is a directed edge from vertex X_i to vertex Y_i.
Initially, all vertices are white.

Process Q queries in order. Each query is of one of the following two types:

• 1 v: Color vertex v black.
• 2 v: Determine whether it is possible to reach a black vertex by following edges from vertex v.

Constraints

• 1\leq N \leq 3\times 10^5
• 0\leq M \leq 3\times 10^5
• 1\leq Q \leq 3\times 10^5
• 1\leq X_i,Y_i \leq N
• There are no self-loops, that is, X_i \neq Y_i.
• There are no multiple edges, that is, (X_i,Y_i) are distinct.
• In queries, 1 \leq v \leq N.
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes
No
Yes

• Initially, the given graph is as shown in the leftmost figure below.
• By the first query, vertex 3 becomes black, as shown in the center figure.
• In the second query, it is possible to reach black vertex 3 from vertex 1.
• In the third query, it is not possible to reach a black vertex from vertex 4.
• By the fourth query, vertex 5 becomes black, as shown in the rightmost figure.
• In the fifth query, it is possible to reach black vertex 5 from vertex 4.

Problem Statement

There are N cells arranged in a row from left to right.
The i-th cell from the left (1\leq i\leq N) is called cell i.
Initially, all cells are painted white.

Process Q queries in order.
The i-th query (1\leq i\leq Q) is as follows:

Two integers (L_i,R_i) (1\leq L_i\leq R_i\leq N) are given.
Paint all cells L_i, L_i+1, \ldots, R_i black.
Here, cells that were painted white are now painted black, and cells that were painted black remain as is.
After that, find the number of cells (among the N cells) that are painted white.

Constraints

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

Sample Input 1

10 5
3 5
8 9
5 8
2 9
6 6

Sample Output 1

7
5
3
2
2

Initially, 10 cells are arranged in a row from left to right.

• The first query paints cells 3,4,5 black. After the operation, the cells painted white are cells 1,2,6,7,8,9,10, which is 7 cells.
• The second query paints cells 8,9 black. After the operation, the cells painted white are 1,2,6,7,10, which is 5 cells.
• The third query paints cells 5,6,7,8 black. After the operation, the cells painted white are 1,2,10, which is 3 cells.
• The fourth query paints cells 2,3,\ldots,9 black. After the operation, the cells painted white are 1,10, which is 2 cells.
• The fifth query paints cell 6 black. After the operation, the cells painted white are cells 1,10, which is 2 cells.

Thus, output 7,5,3,2,2 in this order on each line.

Sample Input 2

1000000000 1
1 500000000

Sample Output 2

500000000

Problem Statement

There are N cat towers arranged in a row from left to right, and the height of the i-th tower from the left (1\leq i\leq N) is P_i.
Here, (P_1,P_2,\ldots,P_N) is a permutation of (1,2,\ldots,N).
The distance between the i-th tower and the j-th tower from the left is defined as \lvert i-j\rvert.

There is one cat, initially on top of the cat tower of height N.
Takahashi wants to exercise this cat by repeatedly choosing and removing towers.

When Takahashi removes a tower, the cat moves as follows:

• If the cat is not on top of the tower being removed, the cat does not move.
• If the cat is on top of the tower being removed and at least one of the towers adjacent to the left or right of that tower exists, the cat moves to the tallest tower (excluding the tower being removed) among the towers that can be reached by repeatedly moving to adjacent towers starting from the tower being removed. At this time, the cat moves the distance between the tower before movement and the tower after movement (the heights of the towers before, after, and during movement do not matter).
• If the cat is on top of the tower being removed and no towers adjacent to the left or right of that tower exist, the cat jumps into Takahashi's arms, and the exercise ends here. In this case, no movement occurs.

Here, the spaces between removed towers are not filled in. That is, the towers adjacent to the i-th tower from the left initially are only the (i-1)-th and (i+1)-th towers from the left (if they exist), and they will never become adjacent to other towers due to the removal of other towers afterward.

Find the maximum possible total distance the cat moves before the exercise ends.

Constraints

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

Sample Input 1

5
5 3 4 1 2

Sample Output 1

5

Initially, the heights of the cat towers are 5,3,4,1,2 from left to right.
Hereafter, the i-th cat tower from the left (1\leq i\leq 5) is called tower i.
Initially, the cat is on tower 1 (height 5).

If Takahashi removes towers in the order 1,2,3,5,4, the cat moves as follows:

• Takahashi removes tower 1. The towers that can be reached by only moving to adjacent towers from tower 1 are towers 2,3,4,5 (excluding tower 1). The cat moves to tower 3 (height 4), which is the tallest among them.
• Takahashi removes tower 2. The cat does not move.
• Takahashi removes tower 3. The towers that can be reached by only moving to adjacent towers from tower 3 are towers 4,5 (excluding tower 3). The cat moves to tower 5 (height 2), which is the tallest among them.
• Takahashi removes tower 5. The towers that can be reached by only moving to adjacent towers from tower 5 are only tower 4 (excluding tower 5). The cat moves to tower 4 (height 1).
• Takahashi removes tower 4. The cat jumps into Takahashi's arms, and the exercise ends.

Here, the cat moves the total distance of \lvert 1-3\rvert+\lvert 3-5\rvert+\lvert 5-4\rvert=5. There is no way to remove towers that makes the total distance moved 6 or more, so output 5.

Sample Input 2

3
1 3 2

Sample Output 2

1

Initially, the heights of the cat towers are 1,3,2 from left to right.
Hereafter, the i-th cat tower from the left (1\leq i\leq 3) is called tower i.
Initially, the cat is on tower 2 (height 3).

If Takahashi removes towers in the order 2,3, the cat moves as follows:

• Takahashi removes tower 2. The towers that can be reached by only moving to adjacent towers from tower 2 are towers 1,3 (excluding tower 2). The cat moves to tower 3 (height 2), which is the tallest among them.
• Takahashi removes tower 3. The cat jumps into Takahashi's arms, and the exercise ends.

Here, the cat moves the total distance of \lvert 2-3\rvert=1, which is the maximum.
Note that after removing tower 2, tower 1 and tower 3 are not considered to be adjacent.

Problem Statement

There are N cells numbered from 1 to N. Initially, no cell is painted with any color.

There are M types of colors, and with the i-th color, you can paint any number of cells you like among cells L_i,L_i+1,\ldots,R_i.

Find the number, modulo 998244353, of ways to paint the cells that satisfy the following condition:

• For every cell i, if that cell is painted with a color, then exactly one of cells i-1 and i+1 is painted with the same color as cell i.
  • Here, cells 0 and N+1 are considered to be not painted with any color.

Constraints

• 1\leq N,M \leq 5\times 10^5
• 1\leq L_i \leq R_i \leq N
• All input values are integers.

Sample Input 1

5 2
1 3
1 5

Sample Output 1

11

The first color can paint cells 1,2,3, and the second color can paint cells 1,2,3,4,5.

There are 11 ways to paint that satisfy the condition, as follows:

Sample Input 2

3 3
1 1
2 2
3 3

Sample Output 2

1

The one way of not painting any cell satisfies the condition.

Sample Input 3

500000 10
1 499999
2 499998
3 499997
4 499996
5 499995
6 499994
7 499993
8 499992
9 499991
10 499990

Sample Output 3

775503999

Find the count modulo 998244353.