P17021 [ROI 2026 Day1] Physical Training

Several students are training in a sports club. At the start of the training, there are $n$ people in the gym, and later $q$ more people join during the class. All $n + q$ students have distinct heights, and we label them from $1$ to $n + q$ in increasing order of height. During training, the students do a ball-passing exercise. They stand in a line from left to right in some order. Depending on this order, some pairs of students form **valid pairs**. For $i < j$, the two students at positions $i$ and $j$ form a valid pair if and only if at least one of the following two conditions holds: - The student at position $i$ is the leftmost among the students to the left of position $j$ who are shorter than the student at position $j$. - The student at position $j$ is the rightmost among the students to the right of position $i$ who are shorter than the student at position $i$. For example, if the students' labels from left to right are $[6, 7, 3, 5, 1, 2]$, then the valid pairs include $(6, 2)$, $(6, 7)$, $(7, 2)$, $(3, 2)$, $(3, 5)$, $(5, 2)$, and $(1, 2)$. This exercise has two difficulty levels, and each level allows its own set of **valid passes**. During an exercise session at any difficulty level, it is forbidden to pass the ball to a student who has already received the ball. At the first difficulty level, a student may only pass the ball to the shorter person among the students that form a valid pair with them. For example, if the line is $[6, 7, 3, 5, 1, 2]$, then student $3$ can only pass to student $2$; student $5$ can pass to $3$ and $2$; student $1$ cannot pass to anyone. At the second difficulty level, a student may pass the ball to anyone who forms a valid pair with them. For example, in the arrangement $[6, 7, 3, 5, 1, 2]$ above, student $3$ can pass to $2$ and $5$; student $5$ can pass to $3$ and $2$; student $1$ can pass to $2$. The exercise proceeds as follows. The coach chooses the difficulty level $t$. One student holds the ball and makes one valid pass. The student who receives the ball makes another valid pass, and so on. Passing continues until no further pass is possible. If there are multiple valid passes available, any one may be chosen, but it is forbidden to pass to a student who has already received the ball in this session. The participants will complete as many valid passes as possible under the chosen difficulty level. Then there are $q$ times when new members join the training. Each newly joined student stands at the far left or the far right of the existing line. After that, the exercise is performed again under the same difficulty level. For the initial group of trainees, and after each new student joins, you need to compute the maximum number of passes that the participants can complete.

The first line contains an integer $t$ ($1 \le t \le 2$), which indicates the difficulty level of the exercise. The second line contains two integers $n$ and $q$ ($1 \le n \le 10^5$, $0 \le q \le 2 \cdot 10^5$), representing the initial number of participants and the number of people who join later. The third line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n + q$), representing the students' labels from left to right at the beginning. It is guaranteed that all labels are distinct. The next $q$ lines describe the joining students. Each line contains a character `L` or `R` and an integer $x$ ($1 \le x \le n + q$), separated by a space. `L` means the student with label $x$ stands at the far left of the line, and `R` means they stand at the far right. It is guaranteed that after each insertion, all student labels are still distinct.

Output an integer on the first line: the answer for the initial $n$ students at difficulty $t$. On the next $q$ lines, output one integer per line: the answer after each new student joins and the exercise is completed again at the same difficulty.

### Explanation In the first sample, an optimal exercise can start from student $5$. The first pass can be to $3$, the second to $2$, and the third to $1$. Adding student $8$ on the left does not increase the maximum number of passes. After adding student $4$ on the right, the exercise can start from $7$ and pass in order to $6$, $4$, $3$, $2$, $1$. In the second sample, it can also start from $5$ and complete four valid passes, in order to $3$, $2$, $7$, $6$. Adding student $8$ on the left does not change the maximum number of passes. After adding student $4$ on the right, for example starting from $7$, it can pass in order to $6$, $4$, $5$, $3$, $2$, $1$. ### Subtasks | Subtask | Points | $t$ | $n$ and $q$ | Additional constraints | Depends on subtasks | |:---:|:---:|:---:|:---:|:---|:---:| | 1 | 6 | $t = 1$ | $n + q \le 16$ | -- | -- | | 2 | 4 | ^ | $n, q \le 100$ | -- | 1 | | 3 | 3 | ^ | $n \le 1000$，$q = 0$ | -- | -- | | 4 | 5 | ^ | $n, q \le 1000$ | -- | 1–3 | | 5 | 3 | ^ | $q = 0$ | -- | 3 | | 6 | 10 | ^ | $n = 1$ | $a_1 = 1$；students join in increasing order of labels | -- | | 7 | 6 | ^ | -- | It is guaranteed that the initial participants, their order, the joining order of the remaining students, and the joining side are all random | -- | | 8 | 5 | ^ | $n, q \le 50\,000$ | -- | 1–4 | | 9 | 8 | ^ | -- | -- | 1–8 | | 10 | 4 | $t = 2$ | $n + q \le 16$ | -- | -- | | 11 | 6 | ^ | $n, q \le 100$ | -- | 10 | | 12 | 5 | ^ | $n \le 1000$，$q = 0$ | -- | -- | | 13 | 9 | ^ | $n, q \le 1000$ | -- | 10–12 | | 14 | 3 | ^ | $q = 0$ | -- | 12 | | 15 | 6 | ^ | $n = 1$ | $a_1 = 1$；students join in increasing order of labels | -- | | 16 | 6 | ^ | -- | It is guaranteed that the initial participants, their order, the joining order of the remaining students, and the joining side are all random | -- | | 17 | 7 | ^ | $n, q \le 50\,000$ | -- | 10–13 | | 18 | 4 | ^ | -- | -- | 10–17 | Translated by DeepSeek V4 Pro. Translated by ChatGPT 5