Problem Statement

Takahashi has a piano with 100 keys arranged in a row. The i-th key from the left is called key i.

He will play music by pressing N keys one by one. For the i-th press, he will press key A_i, using his left hand if S_i= L, and his right hand if S_i= R.

Before starting to play, he can place both of his hands on any keys he likes, and his fatigue level at this point is 0. During the performance, if he moves one hand from key x to key y, the fatigue level increases by |y-x| (conversely, the fatigue level does not increase for any reason other than moving hands). To press a certain key with a hand, that hand must be placed on that key.

Find the minimum possible fatigue level at the end of the performance.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i \leq 100
• N and A_i are integers.
• S_i is L or R.

Sample Input 1

4
3 L
6 R
9 L
1 R

Sample Output 1

11

For example, the performance can be done as follows:

• Initially, place the left hand on key 3 and the right hand on key 6.
• Press key 3 with the left hand.
• Press key 6 with the right hand.
• Move the left hand from key 3 to key 9. The fatigue level increases by |9-3| = 6.
• Move the right hand from key 6 to key 1. The fatigue level increases by |1-6| = 5.
• Press key 9 with the left hand.
• Press key 1 with the right hand.

In this case, the fatigue level at the end of the performance is 6+5 = 11, which is the minimum possible.

Sample Input 2

3
2 L
2 L
100 L

Sample Output 2

98

Sample Input 3

8
22 L
75 L
26 R
45 R
72 R
81 R
47 L
29 R

Sample Output 3

188

Problem Statement

You are given a sequence of length N consisting of integers: A=(A_1,\ldots,A_N).

Find the smallest non-negative integer not in (A_1,\ldots,A_N).

Constraints

• 1 \leq N \leq 2000
• 0 \leq A_i \leq 2000
• All values in input are integers.

Sample Input 1

8
0 3 2 6 2 1 0 0

Sample Output 1

4

The non-negative integers are 0,1,2,3,4,\ldots.
We have 0,1,2,3 in A, but not 4, so the answer is 4.

Sample Input 2

3
2000 2000 2000

Sample Output 2

0

Problem Statement

You have an empty bag. You are given Q queries, which must be processed in order.

There are three types of queries.

• 1 x : Put one ball with the integer x written on it into the bag.
• 2 x : Remove one ball with the integer x written on it from the bag and discard it. It is guaranteed that the bag has a ball with the integer x written on it when this query is given.
• 3 : Print the number of different integers written on the balls in the bag.

Constraints

• 1 \leq Q \leq 2 \times 10^{5}
• 1 \leq x \leq 10^{6}
• When a query of the second type is given, the bag has a ball with the integer x written on it.
• There is at least one query of the third type.
• All input values are integers.

Sample Input 1

8
1 3
1 1
1 4
3
2 1
3
1 5
3

Sample Output 1

3
2
3

Initially, the bag is empty.

For the first query 1 3, a ball with the integer 3 written on it enters the bag.

For the second query 1 1, a ball with the integer 1 written on it enters the bag.

For the third query 1 4, a ball with the integer 4 written on it enters the bag.

For the fourth query 3, the bag has balls with the integers 1, 3, 4, so print 3.

For the fifth query 2 1, a ball with the integer 1 written on it is removed from the bag.

For the sixth query 3, the bag has balls with the integers 3, 4, so print 2.

For the seventh query 1 5, a ball with the integer 5 written on it enters the bag.

For the eighth query 3, the bag has balls with the integers 3, 4, 5, so print 3.

Sample Input 2

8
1 2
1 2
3
2 2
1 4
1 4
2 2
3

Sample Output 2

1
1

Problem Statement

We have a sequence of length N: A=(a_1,\ldots,a_N). Additionally, you are given an integer K.

You can perform the following operation zero or more times.

• Choose an integer i such that 1 \leq i \leq N-K, then swap the values of a_i and a_{i+K}.

Determine whether it is possible to sort A in ascending order.

Constraints

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

Sample Input 1

5 2
3 4 1 3 4

Sample Output 1

Yes

The following sequence of operations sorts A in ascending order.

• Choose i=1 to swap the values of a_1 and a_3. A is now (1,4,3,3,4).
• Choose i=2 to swap the values of a_2 and a_4. A is now (1,3,3,4,4).

Sample Input 2

5 3
3 4 1 3 4

Sample Output 2

No

Sample Input 3

7 5
1 2 3 4 5 5 10

Sample Output 3

Yes

No operations may be needed.

Problem Statement

A sequence of n numbers, S = (s_1, s_2, \dots, s_n), is said to be non-decreasing if and only if s_i \leq s_{i+1} holds for every i (1 \leq i \leq n - 1).

Given are non-decreasing sequences of N integers each: A = (a_1, a_2, \dots, a_N) and B = (b_1, b_2, \dots, b_N).
Consider a non-decreasing sequence of N integers, C = (c_1, c_2, \dots, c_N), that satisfies the following condition:

• a_i \leq c_i \leq b_i for every i (1 \leq i \leq N).

Find the number, modulo 998244353, of sequences that can be C.

Constraints

• 1 \leq N \leq 3000
• 0 \leq a_i \leq b_i \leq 3000 (1 \leq i \leq N)
• The sequences A and B are non-decreasing.
• All values in input are integers.

Sample Input 1

2
1 1
2 3

Sample Output 1

5

There are five sequences that can be C, as follows.

• (1, 1)
• (1, 2)
• (1, 3)
• (2, 2)
• (2, 3)

Note that (2, 1) does not satisfy the condition since it is not non-decreasing.

Sample Input 2

3
2 2 2
2 2 2

Sample Output 2

1

There is one sequence that can be C, as follows.

• (2, 2, 2)

Sample Input 3

10
1 2 3 4 5 6 7 8 9 10
1 4 9 16 25 36 49 64 81 100

Sample Output 3

978222082

Be sure to find the count modulo 998244353.