Problem Statement

Takahashi is tallying the results of his school's final exam.

There are N students in the class, and student i scored A_i points. All scores are integers between 0 and 100, inclusive.

The teacher has set a passing grade of X points. Students who scored X points or more pass, while students who scored less than X points fail and must attend supplementary lessons.

Find the number of students who must attend supplementary lessons, that is, the number of students who scored less than X points.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq X \leq 100
• 0 \leq A_i \leq 100
• All inputs are integers

Sample Input 1

5 60
72 45 60 38 85

Sample Output 1

2

Sample Input 2

8 50
49 50 51 30 75 50 48 100

Sample Output 2

3

Sample Input 3

15 70
65 70 82 55 91 68 70 43 77 69 100 35 88 71 60

Sample Output 3

7

Problem Statement

Takahashi manages a warehouse in the form of a grid with H rows and W columns. The cell at the i-th row from the top (1 \leq i \leq H) and the j-th column from the left (1 \leq j \leq W) is denoted as cell (i, j). Each cell either has a package placed on it or is empty. The state of the warehouse is represented by H strings S_1, S_2, \ldots, S_H, each of length W. If the j-th character of S_i is #, then cell (i, j) has a package; if it is ., the cell is empty.

Takahashi plans to introduce one inspection robot into this warehouse and have it collect packages by moving around. The robot is initially placed at cell (1, 1) (the top-left corner).

The robot is given N instructions in order, represented by a string T of length N. The k-th character of T (1 \leq k \leq N) corresponds to the k-th instruction, and each instruction is one of the following:

• U: Move one cell up (row number decreases by 1)
• D: Move one cell down (row number increases by 1)
• L: Move one cell left (column number decreases by 1)
• R: Move one cell right (column number increases by 1)

However, if the destination of an instruction would be outside the grid, that instruction is ignored, and the robot stays in its current position.

The robot operates as follows:

1. The robot is placed at cell (1, 1). If cell (1, 1) has a package, it is collected (the package is removed from that cell).
2. For k = 1, 2, \ldots, N in order, the k-th instruction is executed. After processing each instruction (whether the robot moved or the instruction was ignored and the robot stayed in place), if there is a package on the cell where the robot is located, it is collected (the package is removed from that cell).

If the robot revisits a cell from which a package has already been collected, nothing happens.

Determine the number of packages remaining in the warehouse after all instructions have been executed.

Constraints

• 1 \leq H \leq 500
• 1 \leq W \leq 500
• 1 \leq N \leq 2 \times 10^5
• H, W, N are integers
• S_i is a string of length W consisting only of # and .
• T is a string of length N consisting only of U, D, L, R

Sample Input 1

3 4 9
#..#
.##.
..#.
RRDDLUUUL

Sample Output 1

1

Sample Input 2

2 3 8
###
..#
UUURRRDD

Sample Output 2

0

Sample Input 3

6 7 30
.#..#..
##...#.
..#.#..
.##....
...###.
#..#..#
RRRDDRULDLURRRDDLLUUURRDDDLURD

Sample Output 3

10

Sample Input 4

12 15 60
#..#...##....#.
.#....#....##..
....##..#...#..
###...#..#.....
..#..#..##..#..
.....#.....#..#
.##..#..#..##..
...#.....##....
#....###...#...
..##..#....#..#
.#...#..#..#...
...#..##.....#.
RRDDLLUUURRRDDLLUUURRRDDLLUUURRRDDLLUUURRRDDLLUUURRRDDLLUUUR

Sample Output 4

46

Sample Input 5

1 1 12
#
UDLRUDLRUDLR

Sample Output 5

0

Problem Statement

Takahashi is in charge of facility management at a school. The school has N classrooms, and each classroom i (1 \leq i \leq N) has one old air conditioner installed. Each classroom's air conditioner has a deterioration level D_i, where a higher deterioration level means the air conditioner is older and has worse performance.

This time, M new air conditioners have arrived. Takahashi can choose 0 or more and M or fewer distinct classrooms from the N classrooms, and replace the old air conditioner in each chosen classroom with one new air conditioner. Each classroom can be replaced at most once, and it is not necessary to use all M new air conditioners. The deterioration level of a classroom where a replacement was made becomes 0, while the deterioration level of a classroom where no replacement was made remains at its original value D_i.

Takahashi wants to choose the classrooms for replacement wisely so as to minimize the maximum deterioration level among all classrooms after the replacements. Find the minimum achievable value of this maximum.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq N
• 0 \leq D_i \leq 10^9
• All input values are integers

Sample Input 1

5 2
3 1 4 1 5

Sample Output 1

3

Sample Input 2

7 7
10 20 30 40 50 60 70

Sample Output 2

0

Sample Input 3

10 3
100 200 300 400 500 600 700 800 900 1000000000

Sample Output 3

700

Problem Statement

Takahashi is guiding a constellation observation tour at an observatory.

On the observation deck of the observatory, N telescopes are installed along a number line. Each telescope is numbered from 1 to N, and telescope i is installed at coordinate X_i. No two telescopes are installed at the same coordinate.

During the tour, participants start in front of telescope S. After that, they repeat the following movement Q times:

• Among the N-1 telescopes excluding the one you are currently at, move to the telescope whose distance (absolute difference of coordinates) from your current position is the smallest. If there are multiple telescopes with the smallest distance, move to the one with the smallest number among them.

Note that returning to the telescope you were at immediately before is not prohibited (only the telescope you are currently at is excluded from the movement candidates).

Determine the number of the telescope where the participant is after Q moves.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq S \leq N
• 1 \leq Q \leq 10^{18}
• -10^9 \leq X_i \leq 10^9
• X_i \neq X_j (i \neq j)
• All inputs are integers

Sample Input 1

3 1 3
1 3 6

Sample Output 1

2

Sample Input 2

4 2 4
0 10 5 20

Sample Output 2

1

Sample Input 3

5 3 1000000000
1 4 6 9 15

Sample Output 3

3

Sample Input 4

10 5 1000000000000000000
-1000000000 -500000000 -100 0 50 100 200 500000000 999999999 1000000000

Sample Output 4

5

Sample Input 5

2 1 1000000000000000000
0 1

Sample Output 5

1

Problem Statement

There are N books arranged in a horizontal row on Takahashi's bookshelf. Initially, the book at the i-th position from the left has a durability of D_i.

Takahashi performs Q operations on this bookshelf in order. In the j-th operation, an integer T_j is given, and the following procedure is carried out:

1. Let M be the number of books currently remaining on the bookshelf.
2. If T_j > M, the T_j-th book from the left does not exist, so nothing happens.
3. If T_j \leq M, the durability of the book currently at the T_j-th position from the left on the bookshelf is decreased by 1. If the durability becomes 0, that book is immediately removed from the bookshelf. All books that were to the right of the removed book shift one position to the left, so that no gaps remain among the remaining books.

After each operation (including cases where nothing happens), output the number of books remaining on the bookshelf.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq T_j \leq N (1 \leq j \leq Q)
• All input values are integers.

Note: T_j is at most the initial number of books N, but it may exceed the number of books M at the time of the operation. In that case, nothing happens as described in step 2 above.

Sample Input 1

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

Sample Output 1

5
4
3
2
2

Sample Input 2

3 4
1 1 1
1
1
1
1

Sample Output 2

2
1
0
0

Sample Input 3

10 10
2 1 3 1 2 1 4 2 1 3
3
5
1
7
2
4
3
1
2
1

Sample Output 3

10
10
10
10
9
8
7
6
5
5

Sample Input 4

20 25
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4
1
3
5
7
2
10
15
1
3
5
8
12
1
1
2
4
6
3
2
1
5
4
3
2
1

Sample Output 4

20
20
20
20
19
19
19
19
18
17
17
17
16
16
16
16
16
16
16
16
16
16
16
16
15

Sample Input 5

1 1
1000000000
1

Sample Output 5

1