Problem Statement

You are given a string S of length N-1 consisting of < and >.

A sequence x=(x_1,x_2,\cdots,x_N) of length N is called a good sequence if and only if it satisfies the following condition:

• For each i (1 \leq i \leq N-1), if the i-th character of S is <, then x_i\lt x_{i+1}; if it is >, then x_i \gt x_{i+1}.

Find the minimum possible inversion number of a good sequence.

Constraints

• 2 \leq N \leq 250000
• S is a string of length N-1 consisting of < and >.
• All input values are integers.

Sample Input 1

4
<><

Sample Output 1

1

x=(1,2,1,2) is a good sequence, and its inversion number is 1. There is no good sequence whose inversion number is 0, so the answer is 1.

Sample Input 2

2
<

Sample Output 2

0

Sample Input 3

10
>>>>>>>>>

Sample Output 3

45

Sample Input 4

30
<<><>>><><>><><><<>><<<><><<>

Sample Output 4

19

Problem Statement

There are N piles of stones, and the i-th pile (1 \leq i \leq N) has A_i stones.

You will choose a positive integer k. Then, Alice and Bob will play a game with these piles as follows.

• Starting with Alice, the players take turns to play.
• In each turn, the player must choose a non-empty pile and remove from it some number of stones between 1 and k, inclusive.

The person who cannot make a move on their turn loses, and the other person wins.

You want to choose a positive integer k for which there is a winning strategy for Alice. Determine if such a k exists. If it exists, determine if there is a maximum value for such k. If the maximum value exists, provide that value.

Constraints

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

Sample Input 1

3
1 2 3

Sample Output 1

2

For example, if k=2, Alice has a winning strategy. If k \geq 3, Alice has no winning strategy, so the answer is k=2.

Sample Input 2

4
1 2 3 4

Sample Output 2

-1

For example, Alice has winning strategies for all k=100,200,300,\cdots. Thus, there is no maximum value for k, so print -1.

Sample Input 3

2
100 100

Sample Output 3

0

No matter what k is chosen, Alice has no winning strategy. Thus, print 0.

Problem Statement

You are given a string S of length N consisting of the characters A, B, and C.

Consider performing the following operation between 0 and K times, inclusive:

• Freely choose two characters in S and swap them.

Find the number of strings that S can be after the operations, modulo 998244353.

Constraints

• 1 \leq N \leq 250000
• 1 \leq K \leq 100
• S is a string of length N consisting of the characters A, B, and C.
• All input values are integers.

Sample Input 1

3 1
ABC

Sample Output 1

4

The following four strings can be obtained:

• S=ABC: No operation is needed.
• S=BAC: Swap the 1-st and 2-nd characters.
• S=CBA: Swap the 1-st and 3-rd characters.
• S=ACB: Swap the 2-nd and 3-rd characters.

Sample Input 2

3 2
ABC

Sample Output 2

6

Sample Input 3

4 5
AAAA

Sample Output 3

1

Sample Input 4

30 10
CACCABAABBABABBCBBCAAACAAACCCA

Sample Output 4

42981885

Problem Statement

There are N squares arranged in a row, numbered 1 to N from left to right. Initially, all squares are white.

You can perform the following M types of operations any number of times in any order:

• Type-i operation: Paint square L_i through square R_i in black.

Find the maximum number of times the operations can change the state of the squares. If an operation changes the color of at least one square, that operation is considered to change the state of the squares.

Constraints

• 1 \leq N \leq 500
• 1 \leq M \leq N(N+1)/2
• 1 \leq L_i \leq R_i \leq N
• (L_i,R_i) \neq (L_j,R_j) for all i \neq j
• All input values are integers.

Sample Input 1

3 3
1 3
1 1
3 3

Sample Output 1

3

If you perform the operations as follows, they will change the state of the squares three times.

• Perform type-2 operation. Square 1 is newly painted black.
• Perform type-3 operation. Square 3 is newly painted black.
• Perform type-1 operation. Square 2 is newly painted black.

Sample Input 2

4 3
1 2
3 4
1 4

Sample Output 2

2

Sample Input 3

5 5
4 5
1 1
2 4
1 2
2 5

Sample Output 3

4

Sample Input 4

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

Sample Output 4

11

Problem Statement

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

Consider dividing this sequence into K non-empty contiguous subsequences. Among these K contiguous subsequences, the number of ones whose sum of elements is at least S will be called the score. Find the maximum value of the score.

Constraints

• 1 \leq K \leq N \leq 250000
• 1 \leq A_i \leq 10^9
• 1 \leq S \leq 10^{15}
• All input values are integers.

Sample Input 1

4 3 6
1 4 2 8

Sample Output 1

2

If the sequence is divided into (1),(4,2),(8), the score will be 2. No higher score can be achieved, so the answer is 2.

Sample Input 2

10 5 2
1 1 1 1 1 1 1 1 1 1

Sample Output 2

5

Sample Input 3

10 5 3
1 1 1 1 1 1 1 1 1 1

Sample Output 3

2

Sample Input 4

20 6 946667802
786820955 250480341 710671229 946667801 19271059 404902145 251317818 22712439 520643153 344670307 274195604 561032101 140039457 543856068 521915711 857077284 499774361 419370025 744280520 249168130

Sample Output 4

6

Problem Statement

For an integer sequence x=(x_1,x_2,\cdots,x_N) of length N with each element being between 0 and M, inclusive, we define f(x) as follows:

• Prepare an integer sequence y=(y_1,y_2,\cdots,y_M) of length M. Initially, set all elements of y to 0. Then, for each i=1,2,\cdots,N, in order, perform the following operations:
  • For each integer j (1 \leq j \leq x_i), replace the value of y_j with \max(y_j-1,0).
  • For each integer j (x_i < j \leq M), replace the value of y_j with y_j+1.
• The sum of the elements of y after all operations is the value of f(x).

You are given an integer sequence A=(A_1,A_2,\cdots,A_N) of length N with each element being between 0 and M, inclusive. Process Q queries:

• The i-th query: Given integers X_i and Y_i, replace the value of A_{X_i} with Y_i. Then, print the value of f(A).

Constraints

• 1 \leq N,M,Q \leq 250000
• 0 \leq A_i \leq M
• 1 \leq X_i \leq N
• 0 \leq Y_i \leq M
• All input values are integers.

Sample Input 1

3 4 2
1 2 3
1 4
3 0

Sample Output 1

2
6

Consider the first query. We replace the value of A_1 with 4, making A=(4,2,3). Then, the value of f(A) is calculated as follows:

• Prepare y=(0,0,0,0).
• Perform the operation for A_1=4, resulting in y=(0,0,0,0).
• Perform the operation for A_2=2, resulting in y=(0,0,1,1).
• Perform the operation for A_3=3, resulting in y=(0,0,0,2).
• The sum of the elements of y, which equals 2, is the value of f(A).

Next, consider the second query. We replace the value of A_3 with 0, making A=(4,2,0). Then, the value of f(A) is calculated as follows:

• Prepare y=(0,0,0,0).
• Perform the operation for A_1=4, resulting in y=(0,0,0,0).
• Perform the operation for A_2=2, resulting in y=(0,0,1,1).
• Perform the operation for A_3=0, resulting in y=(1,1,2,2).
• The sum of the elements of y, which equals 6, is the value of f(A).

Sample Input 2

7 2 9
2 0 2 2 0 1 0
1 1
3 0
4 0
4 1
6 1
3 2
2 0
3 2
2 0

Sample Output 2

4
7
11
9
9
6
6
6
6

Sample Input 3

20 200000 10
39664 143179 193565 153887 16141 91985 51452 155409 116777 190060 87620 64458 106481 51272 9108 100995 139248 18243 181424 6182
4 196305
13 59753
8 96194
6 57037
19 125781
16 142779
15 13967
10 17772
16 84763
12 17283

Sample Output 3

1145670
1234421
1352851
1352851
1464137
1380569
1380569
1608611
1724643
1736769