Several students are participating in a sports club. At the beginning of the training, there are $n$ people in the gym, and then $q$ more people join them one by one during the session. The heights of all $n+q$ students are distinct; let us number the students from $1$ to $n+q$ in increasing order of their height.

During the training, the students perform exercises with a ball. The students line up in a row from left to right in some order. Depending on the order in which they are lined up, some pairs of students form \textit{valid pairs}.

A pair of students standing at positions $i$ and $j$, where $i < j$, forms a valid pair if one of the two following conditions is met: the student at position $i$ is the leftmost student among those who are shorter than the student at position $j$ and stand to the left of them; the student at position $j$ is the rightmost student among those who are shorter than the student at position $i$ and stand to the right of them.

For example, if students with numbers $[6, 7, 3, 5, 1, 2]$ are standing in a row, the valid pairs are $(6, 2)$, $(6, 7)$, $(7, 2)$, $(3, 2)$, $(3, 5)$, $(5, 2)$, and $(1, 2)$.

The exercise has two difficulty levels, each with its own \textit{valid throws}. When performing the exercise at any difficulty level, it is forbidden to throw the ball to a student who has already held the ball during the current exercise.

At the first difficulty level, a student can throw the ball to any student with whom they form a valid pair and who is shorter than them. For example, if students with numbers $[6, 7, 3, 5, 1, 2]$ are standing in a row, the student with number $3$ can only throw the ball to the student with number $2$, the student with number $5$ can throw to students with numbers $3$ and $2$, and the student with number $1$ cannot throw the ball to anyone.

At the second difficulty level, a student can throw the ball to any student with whom they form a valid pair. For example, if students with numbers $[6, 7, 3, 5, 1, 2]$ are standing in a row, the student with number $3$ can throw the ball to students with numbers $2$ and $5$, the student with number $5$ can throw to students with numbers $3$ and $2$, and the student with number $1$ can throw the ball to the student with number $2$.

The exercise is performed as follows. The coach chooses the difficulty level $t$. One of the students takes the ball and makes a valid throw. The student who receives the ball then makes a valid throw, and so on. Throws are performed as long as possible. If there are multiple valid throws, any of them can be chosen, but it is forbidden to throw the ball to a student who has already held the ball during the current exercise. The participants at the training perform the valid throws for the chosen difficulty level in such a way that the maximum number of throws is made.

Then, $q$ times, one more student joins the training. They stand either to the right or to the left of those already performing the exercise. After this, the exercise is performed again at the same difficulty level.

For the initial set of participants and after the addition of each new student, it is necessary to determine the maximum number of throws the training participants can make.

Input

The first line contains a single integer $t$ ($1 \le t \le 2$) — the difficulty level of the exercise.

The second line contains two integers $n$ and $q$ ($1 \leq n \leq 10^{5}$, $0 \leq q \leq 2 \cdot 10^{5}$) — the initial number of participants and the number of participants who will join.

The third line contains $n$ integers $a_{1}, a_{2}, \ldots, a_{n}$ ($1 \leq a_{i} \leq n + q$) — the numbers of the participants initially standing in the row from left to right. It is guaranteed that all numbers are distinct.

The next $q$ lines contain the numbers of the participants joining the exercise. Each line contains a character 'L' or 'R' and an integer $x$ separated by a space ($1\le x\le n + q$). The letter 'L' means the student with number $x$ stands at the left of the row, and 'R' means at the right.

It is guaranteed that after each addition, all participant numbers are distinct.

Output

In the first line, output a single number — the answer to the problem for the initial $n$ participants and exercise difficulty $t$.

In the next $q$ lines, output one integer each — the answer to the problem after adding each of the $q$ participants and performing the exercise at the same difficulty level.

Examples

Input 1

1
3 2
6 3 2
L 8
R 4

Output 1

2
2
3

Input 2

2
3 2
6 3 2
L 8
R 4

Output 2

2
2
4

Note

In the first example, it is optimal to start the exercise, for example, with the participant numbered 5. The first throw can be to the participant numbered 3, the second to the participant numbered 2, and the third to the participant numbered 1. Adding participant 8 to the left does not increase the maximum number of throws. Adding participant 4 to the right allows, starting from the participant numbered 7, to sequentially throw the ball to participants numbered 6, 4, 3, 2, and 1.

In the second example, one can also start with the participant numbered 5 and get four valid throws to participants numbered 3, 2, 7, and 6. Adding participant 8 to the left does not change the maximum number of throws, and adding participant 4 to the right allows, starting from, for example, number 7, to sequentially throw the ball to participants numbered 6, 4, 5, 3, 2, and 1.

Subtasks