Le Nain Gardien de zoo a récemment été promu chef du Pavillon des Renards au zoo de Wrocław. Son amour pour le renard (ou lis, comme on l'appelle en polonais) ne connaît pas de limites.
Le nain s'occupe d'une longue rangée de renards dans des enclos disposés le long de l'allée principale. Chaque renard a une valeur de magnificence, et le nain est fier de trouver la Plus Longue Sous-séquence Croissante (LIS) de magnificence parmi ses renards.
Aujourd'hui, le nain transfère certains renards vers d'autres zoos et les remplace par des renards que les autres zoos ont envoyés en retour. Au début de la journée, le Nain Gardien de zoo se tient avec un chariot de nouveaux renards à côté du premier enclos (le plus à gauche). Le nain marchera le long de l'allée, se déplaçant d'enclos en enclos. Parfois, il s'arrêtera devant l'un des enclos et remplacera le renard qui s'y trouve par un autre renard, ayant éventuellement une magnificence différente. Chaque fois que cela se produit, il doit immédiatement calculer la longueur de la plus longue sous-séquence croissante de magnificence. Pouvez-vous l'aider à suivre ce nombre ?
Entrée
La première ligne de l'entrée contient deux entiers $N$ et $Q$, représentant le nombre d'enclos le long de l'allée et le nombre d'actions effectuées par le nain.
La deuxième ligne de l'entrée contient $N$ entiers $m_1, m_2, \dots, m_N$, décrivant la magnificence initiale de chaque renard.
Les $Q$ lignes suivantes décrivent les actions. Une action unique est l'une des suivantes :
<— le nain se déplace d'un enclos vers la gauche,>— le nain se déplace d'un enclos vers la droite,! v— le nain échange le renard de l'enclos actuel contre un renard de magnificence $v$.
Sortie
Pour chaque action !, affichez une seule ligne contenant la longueur de la plus longue sous-séquence croissante de la magnificence des renards.
Contraintes
$2 \le N \le 200\,000$, $1 \le Q \le 500\,000$, $1 \le m_i \le 10^6$, $1 \le v \le 10^6$.
Exemples
Entrée 1
5 8 3 4 1 7 2 > ! 2 > > > ! 10 < ! 11
Sortie 1
2 3 2
Note
Tout d'abord, le Nain Gardien de zoo se déplace vers le deuxième enclos et échange le renard contre un autre de magnificence $2$. La longueur de la plus longue sous-séquence croissante est $2$. Ensuite, il se déplace vers le cinquième enclos et échange le renard contre un autre de magnificence $10$, et la longueur de la LIS devient $3$. Enfin, le Gardien de zoo se déplace vers le quatrième enclos et change la magnificence en $11$, ce qui ramène la longueur de la LIS à $2$.