Problem Statement

Given is a string S of length N-1. Each character in S is < or >.

A sequence of N non-negative integers, a_1,a_2,\cdots,a_N, is said to be good when the following condition is satisfied for all i (1 \leq i \leq N-1):

• If S_i= <: a_i<a_{i+1}
• If S_i= >: a_i>a_{i+1}

Find the minimum possible sum of the elements of a good sequence of N non-negative integers.

Constraints

• 2 \leq N \leq 5 \times 10^5
• S is a string of length N-1 consisting of < and >.

Sample Input 1

<>>

Sample Output 1

3

a=(0,2,1,0) is a good sequence whose sum is 3. There is no good sequence whose sum is less than 3.

Sample Input 2

<>>><<><<<<<>>><

Sample Output 2

28

Problem Statement

10^9 contestants, numbered 1 to 10^9, will compete in a competition. There will be two contests in this competition.

The organizer prepared N problems, numbered 1 to N, to use in these contests. When Problem i is presented in a contest, it will be solved by all contestants from Contestant L_i to Contestant R_i (inclusive), and will not be solved by any other contestants.

The organizer will use these N problems in the two contests. Each problem must be used in exactly one of the contests, and each contest must have at least one problem.

The joyfulness of each contest is the number of contestants who will solve all the problems in the contest. Find the maximum possible total joyfulness of the two contests.

Constraints

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

Sample Input 1

4
4 7
1 4
5 8
2 5

Sample Output 1

6

The optimal choice is:

• Use Problem 1 and 3 in the first contest. Contestant 5, 6, and 7 will solve both of them, so the joyfulness of this contest is 3.
• Use Problem 2 and 4 in the second contest. Contestant 2, 3, and 4 will solve both of them, so the joyfulness of this contest is 3.
• The total joyfulness of these two contests is 6. We cannot make the total joyfulness greater than 6.

Sample Input 2

4
1 20
2 19
3 18
4 17

Sample Output 2

34

Sample Input 3

10
457835016 996058008
456475528 529149798
455108441 512701454
455817105 523506955
457368248 814532746
455073228 459494089
456651538 774276744
457667152 974637457
457293701 800549465
456580262 636471526

Sample Output 3

540049931

Problem Statement

Given is a positive even number N.

Find the number of strings s of length N consisting of A, B, and C that satisfy the following condition:

• s can be converted to the empty string by repeating the following operation:
  • Choose two consecutive characters in s and erase them. However, choosing AB or BA is not allowed.

For example, ABBC satisfies the condition for N=4, because we can convert it as follows: ABBC → (erase BB) → AC → (erase AC) → (empty).

The answer can be enormous, so compute the count modulo 998244353.

Constraints

• 2 \leq N \leq 10^7
• N is an even number.

Sample Input 1

2

Sample Output 1

7

Except AB and BA, all possible strings satisfy the conditions.

Sample Input 2

10

Sample Output 2

50007

Sample Input 3

1000000

Sample Output 3

210055358

Problem Statement

We have N balance beams numbered 1 to N. The length of each beam is 1 meters. Snuke walks on Beam i at a speed of 1/A_i meters per second, and Ringo walks on Beam i at a speed of 1/B_i meters per second.

Snuke and Ringo will play the following game:

• First, Snuke connects the N beams in any order of his choice and makes a long beam of length N meters.
• Then, Snuke starts at the left end of the long beam. At the same time, Ringo starts at a point chosen uniformly at random on the long beam. Both of them walk to the right end of the long beam.
• Snuke wins if and only if he catches up to Ringo before Ringo reaches the right end of the long beam. That is, Snuke wins if there is a moment when Snuke and Ringo stand at the same position, and Ringo wins otherwise.

Find the probability that Snuke wins when Snuke arranges the N beams so that the probability of his winning is maximized.

This probability is a rational number, so we ask you to represent it as an irreducible fraction P/Q (to represent 0, use P=0, Q=1).

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i,B_i \leq 10^9
• All values in input are integers.

Sample Input 1

2
3 2
1 2

Sample Output 1

1 4

When the beams are connected in the order 2,1 from left to right, the probability of Snuke's winning is 1/4, which is the maximum possible value.

Sample Input 2

4
1 5
4 7
2 1
8 4

Sample Output 2

1 2

Sample Input 3

3
4 1
5 2
6 3

Sample Output 3

0 1

Sample Input 4

10
866111664 178537096
705445072 318106937
472381277 579910117
353498483 865935868
383133839 231371336
378371075 681212831
304570952 16537461
955719384 267238505
844917655 218662351
550309930 62731178

Sample Output 4

697461712 2899550585

Problem Statement

Snuke has a sequence of N integers x_1,x_2,\cdots,x_N. Initially, all the elements are 0.

He can do the following two kinds of operations any number of times in any order:

• Operation 1: choose an integer k (1 \leq k \leq N) and a non-decreasing sequence of k non-negative integers c_1,c_2,\cdots,c_k. Then, for each i (1 \leq i \leq k), replace x_i with x_i+c_i.
• Operation 2: choose an integer k (1 \leq k \leq N) and a non-increasing sequence of k non-negative integers c_1,c_2,\cdots,c_k. Then, for each i (1 \leq i \leq k), replace x_{N-k+i} with x_{N-k+i}+c_i.

His objective is to have x_i=A_i for all i. Find the minimum number of operations required to achieve it.

Constraints

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

Sample Input 1

5
1 2 1 2 1

Sample Output 1

3

One way to achieve the objective in three operations is shown below. The objective cannot be achieved in less than three operations.

• Do Operation 1 and choose k=2,c=(1,2). Now we have x=(1,2,0,0,0).
• Do Operation 1 and choose k=3,c=(0,0,1). Now we have x=(1,2,1,0,0).
• Do Operation 2 and choose k=2,c=(2,1). Now we have x=(1,2,1,2,1).

Sample Input 2

5
2 1 2 1 2

Sample Output 2

2

Sample Input 3

15
541962451 761940280 182215520 378290929 211514670 802103642 28942109 641621418 380343684 526398645 81993818 14709769 139483158 444795625 40343083

Sample Output 3

7

Problem Statement

We have two indistinguishable pieces placed on a number line. Both pieces are initially at coordinate 0. (They can occupy the same position.)

We can do the following two kinds of operations:

• Choose a piece and move it to the right (the positive direction) by 1.
• Move the piece with the smaller coordinate to the position of the piece with the greater coordinate. If two pieces already occupy the same position, nothing happens, but it still counts as doing one operation.

We want to do a total of N operations of these kinds in some order so that one of the pieces will be at coordinate A and the other at coordinate B. Find the number of ways to move the pieces to achieve it. The answer can be enormous, so compute the count modulo 998244353.

Two ways to move the pieces are considered different if and only if there exists an integer i (1 \leq i \leq N) such that the set of the coordinates occupied by the pieces after the i-th operation is different in those two ways.

Constraints

• 1 \leq N \leq 10^7
• 0 \leq A \leq B \leq N
• All values in input are integers.

Sample Input 1

5 1 3

Sample Output 1

4

Shown below are the four ways to move the pieces, where (x,y) represents the state where the two pieces are at coordinates x and y.

• (0,0)→(0,0)→(0,1)→(0,2)→(0,3)→(1,3)
• (0,0)→(0,0)→(0,1)→(0,2)→(1,2)→(1,3)
• (0,0)→(0,0)→(0,1)→(1,1)→(1,2)→(1,3)
• (0,0)→(0,1)→(1,1)→(1,1)→(1,2)→(1,3)

Sample Input 2

10 0 0

Sample Output 2

1

Sample Input 3

10 4 6

Sample Output 3

197

Sample Input 4

1000000 100000 200000

Sample Output 4

758840509