Plusieurs étudiants participent à un club sportif. Au début de l’entraînement, il y a $n$ personnes dans la salle, puis $q$ autres personnes les rejoignent une par une au cours de la séance. Les tailles des $n+q$ étudiants sont toutes distinctes ; numérotons les étudiants de $1$ à $n+q$ par ordre croissant de leur taille.

Pendant l’entraînement, les étudiants effectuent des exercices avec un ballon. Les étudiants se placent en rangée de gauche à droite dans un certain ordre. Selon l’ordre dans lequel ils sont alignés, certaines paires d’étudiants forment des paires valides.

Une paire d’étudiants placés aux positions $i$ et $j$, avec $i < j$, forme une paire valide si l’une des deux conditions suivantes est satisfaite :

• l’étudiant à la position $i$ est l’étudiant le plus à gauche parmi ceux qui sont plus petits que l’étudiant à la position $j$ et qui se trouvent à sa gauche ;
• l’étudiant à la position $j$ est l’étudiant le plus à droite parmi ceux qui sont plus petits que l’étudiant à la position $i$ et qui se trouvent à sa droite.

Par exemple, si les étudiants dont les numéros sont $[6, 7, 3, 5, 1, 2]$ sont alignés, les paires valides sont $(6, 2)$, $(6, 7)$, $(7, 2)$, $(3, 2)$, $(3, 5)$, $(5, 2)$ et $(1, 2)$.

L’exercice a deux niveaux de difficulté, chacun avec ses propres lancers valides. Lors de l’exécution de l’exercice à n’importe quel niveau de difficulté, il est interdit de lancer le ballon à un étudiant qui a déjà eu le ballon pendant l’exercice en cours.

Au premier niveau de difficulté, un étudiant peut lancer le ballon à tout étudiant avec lequel il forme une paire valide et qui est plus petit que lui. Par exemple, si les étudiants dont les numéros sont $[6, 7, 3, 5, 1, 2]$ sont alignés, l’étudiant numéro $3$ ne peut lancer le ballon qu’à l’étudiant numéro $2$, l’étudiant numéro $5$ peut lancer aux étudiants numéros $3$ et $2$, et l’étudiant numéro $1$ ne peut lancer le ballon à personne.

Au deuxième niveau de difficulté, un étudiant peut lancer le ballon à tout étudiant avec lequel il forme une paire valide. Par exemple, si les étudiants dont les numéros sont $[6, 7, 3, 5, 1, 2]$ sont alignés, l’étudiant numéro $3$ peut lancer le ballon aux étudiants numéros $2$ et $5$, l’étudiant numéro $5$ peut lancer aux étudiants numéros $3$ et $2$, et l’étudiant numéro $1$ peut lancer le ballon à l’étudiant numéro $2$.

L’exercice se déroule comme suit. L’entraîneur choisit le niveau de difficulté $t$. Un des étudiants prend le ballon et effectue un lancer valide. L’étudiant qui reçoit le ballon effectue ensuite un lancer valide, et ainsi de suite. Les lancers sont effectués aussi longtemps que possible. S’il y a plusieurs lancers valides, n’importe lequel peut être choisi, mais il est interdit de lancer le ballon à un étudiant qui a déjà eu le ballon pendant l’exercice en cours. Les participants à l’entraînement effectuent les lancers valides pour le niveau de difficulté choisi de manière à réaliser le nombre maximum de lancers.

Ensuite, $q$ fois, un étudiant supplémentaire rejoint l’entraînement. Il se place soit à droite, soit à gauche de ceux qui exécutent déjà l’exercice. Après cela, l’exercice est à nouveau effectué au même niveau de difficulté.

Pour l’ensemble initial de participants et après l’ajout de chaque nouvel étudiant, il faut déterminer le nombre maximum de lancers que les participants à l’entraînement peuvent réaliser.

Entrée

La première ligne contient un seul entier $t$ ($1 \le t \le 2$) — le niveau de difficulté de l’exercice.

La deuxième ligne contient deux entiers $n$ et $q$ ($1 \leq n \leq 10^{5}$, $0 \leq q \leq 2 \cdot 10^{5}$) — le nombre initial de participants et le nombre de participants qui vont rejoindre.

La troisième ligne contient $n$ entiers $a_{1}, a_{2}, \ldots, a_{n}$ ($1 \leq a_{i} \leq n + q$) — les numéros des participants initialement placés dans la rangée de gauche à droite. Il est garanti que tous les numéros sont distincts.

Les $q$ lignes suivantes contiennent les numéros des participants qui rejoignent l’exercice. Chaque ligne contient un caractère 'L' ou 'R' et un entier $x$ séparés par une espace ($1\le x\le n + q$). La lettre 'L' signifie que l’étudiant de numéro $x$ se place à gauche de la rangée, et 'R' signifie à droite.

Il est garanti qu’après chaque ajout, tous les numéros des participants sont distincts.

Sortie

Sur la première ligne, affichez un seul nombre — la réponse au problème pour les $n$ participants initiaux et le niveau de difficulté $t$.

Sur les $q$ lignes suivantes, affichez un entier par ligne — la réponse au problème après l’ajout de chacun des $q$ participants et l’exécution de l’exercice au même niveau de difficulté.

Exemples

Entrée 1

1
3 2
6 3 2
L 8
R 4

Sortie 1

2
2
3

Entrée 2

2
3 2
6 3 2
L 8
R 4

Sortie 2

2
2
4

Remarque

Dans le premier exemple, il est optimal de commencer l’exercice, par exemple, avec le participant numéro 5. Le premier lancer peut être au participant numéro 3, le deuxième au participant numéro 2, et le troisième au participant numéro 1. L’ajout du participant 8 à gauche n’augmente pas le nombre maximum de lancers. L’ajout du participant 4 à droite permet, en commençant par le participant numéro 7, de lancer successivement le ballon aux participants numéros 6, 4, 3, 2 et 1.

Dans le second exemple, on peut aussi commencer avec le participant numéro 5 et obtenir quatre lancers valides vers les participants numéros 3, 2, 7 et 6. L’ajout du participant 8 à gauche ne change pas le nombre maximum de lancers, et l’ajout du participant 4 à droite permet, en commençant par exemple par le numéro 7, de lancer successivement le ballon aux participants numéros 6, 4, 5, 3, 2 et 1.

Sous-tâches