Varios estudiantes participan en un club deportivo. Al comienzo del entrenamiento, hay $n$ personas en el gimnasio, y luego se les unen $q$ personas más una por una durante la sesión. Las alturas de todos los $n+q$ estudiantes son distintas; numeremos los estudiantes de $1$ a $n+q$ en orden creciente de su altura.
Durante el entrenamiento, los estudiantes realizan ejercicios con un balón. Los estudiantes se colocan en una fila de izquierda a derecha en algún orden. Dependiendo del orden en que estén colocados, algunos pares de estudiantes forman pares válidos.
Un par de estudiantes que se encuentran en las posiciones $i$ y $j$, donde $i < j$, forma un par válido si se cumple una de las dos condiciones siguientes:
- el estudiante en la posición $i$ es el estudiante más a la izquierda entre aquellos que son más bajos que el estudiante en la posición $j$ y están a su izquierda;
- el estudiante en la posición $j$ es el estudiante más a la derecha entre aquellos que son más bajos que el estudiante en la posición $i$ y están a su derecha.
Por ejemplo, si los estudiantes con números $[6, 7, 3, 5, 1, 2]$ están colocados en una fila, los pares válidos son $(6, 2)$, $(6, 7)$, $(7, 2)$, $(3, 2)$, $(3, 5)$, $(5, 2)$ y $(1, 2)$.
El ejercicio tiene dos niveles de dificultad, cada uno con sus propios lanzamientos válidos. Al realizar el ejercicio en cualquier nivel de dificultad, está prohibido lanzar el balón a un estudiante que ya haya tenido el balón durante el ejercicio actual.
En el primer nivel de dificultad, un estudiante puede lanzar el balón a cualquier estudiante con quien forme un par válido y que sea más bajo que él. Por ejemplo, si los estudiantes con números $[6, 7, 3, 5, 1, 2]$ están colocados en una fila, el estudiante con número $3$ solo puede lanzar el balón al estudiante con número $2$, el estudiante con número $5$ puede lanzar a los estudiantes con números $3$ y $2$, y el estudiante con número $1$ no puede lanzar el balón a nadie.
En el segundo nivel de dificultad, un estudiante puede lanzar el balón a cualquier estudiante con quien forme un par válido. Por ejemplo, si los estudiantes con números $[6, 7, 3, 5, 1, 2]$ están colocados en una fila, el estudiante con número $3$ puede lanzar el balón a los estudiantes con números $2$ y $5$, el estudiante con número $5$ puede lanzar a los estudiantes con números $3$ y $2$, y el estudiante con número $1$ puede lanzar el balón al estudiante con número $2$.
El ejercicio se realiza de la siguiente manera. El entrenador elige el nivel de dificultad $t$. Uno de los estudiantes toma el balón y realiza un lanzamiento válido. El estudiante que recibe el balón realiza entonces un lanzamiento válido, y así sucesivamente. Los lanzamientos se realizan mientras sea posible. Si hay varios lanzamientos válidos, se puede elegir cualquiera, pero está prohibido lanzar el balón a un estudiante que ya haya tenido el balón durante el ejercicio actual. Los participantes del entrenamiento realizan los lanzamientos válidos para el nivel de dificultad elegido de manera que se haga el máximo número de lanzamientos.
Luego, $q$ veces, un estudiante más se une al entrenamiento. Se coloca ya sea a la derecha o a la izquierda de los que ya están realizando el ejercicio. Después de esto, el ejercicio se realiza nuevamente al mismo nivel de dificultad.
Para el conjunto inicial de participantes y después de la adición de cada nuevo estudiante, es necesario determinar el número máximo de lanzamientos que pueden hacer los participantes del entrenamiento.
Entrada
La primera línea contiene un único entero $t$ ($1 \le t \le 2$) — el nivel de dificultad del ejercicio.
La segunda línea contiene dos enteros $n$ y $q$ ($1 \leq n \leq 10^{5}$, $0 \leq q \leq 2 \cdot 10^{5}$) — el número inicial de participantes y el número de participantes que se unirán.
La tercera línea contiene $n$ enteros $a_{1}, a_{2}, \ldots, a_{n}$ ($1 \leq a_{i} \leq n + q$) — los números de los participantes que están inicialmente en la fila de izquierda a derecha. Está garantizado que todos los números son distintos.
Las siguientes $q$ líneas contienen los números de los participantes que se unen al ejercicio. Cada línea contiene un carácter 'L' o 'R' y un entero $x$ separados por un espacio ($1\le x\le n + q$). La letra 'L' significa que el estudiante con número $x$ se coloca a la izquierda de la fila, y 'R' significa a la derecha.
Está garantizado que después de cada adición, todos los números de participantes son distintos.
Salida
En la primera línea, imprime un único número — la respuesta al problema para los $n$ participantes iniciales y el nivel de dificultad $t$.
En las siguientes $q$ líneas, imprime un entero cada una — la respuesta al problema después de agregar cada uno de los $q$ participantes y realizar el ejercicio al mismo nivel de dificultad.
Ejemplos
Entrada 1
1 3 2 6 3 2 L 8 R 4
Salida 1
2 2 3
Entrada 2
2 3 2 6 3 2 L 8 R 4
Salida 2
2 2 4
Nota
En el primer ejemplo, es óptimo comenzar el ejercicio, por ejemplo, con el participante numerado 5. El primer lanzamiento puede ser al participante numerado 3, el segundo al participante numerado 2 y el tercero al participante numerado 1. Agregar al participante 8 a la izquierda no aumenta el número máximo de lanzamientos. Agregar al participante 4 a la derecha permite, comenzando desde el participante numerado 7, lanzar secuencialmente el balón a los participantes numerados 6, 4, 3, 2 y 1.
En el segundo ejemplo, también se puede comenzar con el participante numerado 5 y obtener cuatro lanzamientos válidos hacia los participantes numerados 3, 2, 7 y 6. Agregar al participante 8 a la izquierda no cambia el número máximo de lanzamientos, y agregar al participante 4 a la derecha permite, comenzando desde, por ejemplo, el número 7, lanzar secuencialmente el balón a los participantes numerados 6, 4, 5, 3, 2 y 1.
Subtareas
| Subtarea | Puntos | $t$ | $n, q$ | Restricciones adicionales | Subtareas requeridas |
|---|---|---|---|---|---|
| 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$. Los estudiantes se agregan en orden creciente de sus números | -- | |
| 7 | 6 | -- | El conjunto inicial de participantes, su orden, el orden de adición del resto y el lado de adición son aleatorios | -- | |
| 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$. Los estudiantes se agregan en orden creciente de sus números | -- | |
| 16 | 6 | -- | El conjunto inicial de participantes, su orden, el orden de adición del resto y el lado de adición son aleatorios | -- | |
| 17 | 7 | $n, q \le 50\,000$ | -- | 10--13 | |
| 18 | 4 | -- | -- | 10--17 |