Il Nano Guardiano dello Zoo è stato recentemente promosso a capo del Padiglione delle Volpi allo Zoo di Breslavia (Wrocław). Il suo amore per la volpe (o lis, come viene chiamata in polacco) non conosce confini.
Il nano si prende cura di una lunga fila di volpi in recinti disposti lungo il viale principale. Ogni volpe ha un valore di magnificenza, e il nano è orgoglioso di trovare la Più Lunga Sottosequenza Crescente (LIS) di magnificenza tra le sue volpi.
Oggi, il nano sta trasferendo alcune volpi in altri zoo e le sta sostituendo con volpi che gli altri zoo hanno inviato in cambio. All'inizio della giornata, il Nano Guardiano dello Zoo si trova con un carrello di nuove volpi accanto al primo recinto (quello più a sinistra). Il nano camminerà lungo il viale, spostandosi da un recinto all'altro. A volte si fermerà davanti a uno dei recinti e sostituirà la volpe che si trova lì con un'altra volpe, possibilmente con una magnificenza diversa. Ogni volta che ciò accade, deve calcolare immediatamente la lunghezza della più lunga sottosequenza crescente di magnificenza. Puoi aiutarlo a tenere traccia di questo numero?
Input
La prima riga di input contiene due interi $N$ e $Q$, che rappresentano il numero di recinti lungo il viale e il numero di azioni compiute dal nano.
La seconda riga di input contiene $N$ interi $m_1, m_2, \dots, m_N$, che descrivono la magnificenza iniziale di ciascuna volpe.
Le successive $Q$ righe descrivono le azioni. Una singola azione è una delle seguenti:
<— il nano si sposta di un recinto a sinistra,>— il nano si sposta di un recinto a destra,! v— il nano scambia la volpe nel recinto corrente con una volpe di magnificenza $v$.
Output
Per ogni azione !, stampa una singola riga contenente la lunghezza della più lunga sottosequenza crescente della magnificenza delle volpi.
Limiti
$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$.
Esempi
Input 1
5 8 3 4 1 7 2 > ! 2 > > > ! 10 < ! 11
Output 1
2 3 2
Note
Per prima cosa, il Nano Guardiano dello Zoo si sposta al secondo recinto e scambia la volpe con una di magnificenza $2$. La lunghezza della più lunga sottosequenza crescente è $2$. Poi si sposta al quinto recinto e scambia la volpe con una di magnificenza $10$, e la lunghezza della LIS diventa $3$. Infine, il Guardiano dello Zoo si sposta al quarto recinto e cambia la magnificenza in $11$, facendo tornare la lunghezza della LIS a $2$.