Zwerg der Tierpfleger wurde kürzlich zum Leiter des Fuchspavillons im Breslauer Zoo (Wrocław) befördert. Seine Liebe zum Fuchs (oder lis, wie er auf Polnisch heißt) kennt keine Grenzen.

Der Zwerg kümmert sich um eine lange Reihe von Füchsen in Gehegen, die entlang des Hauptweges angeordnet sind. Jeder Fuchs hat einen Prachtwert (magnificence), und der Zwerg ist stolz darauf, die längste aufsteigende Teilfolge (LIS) der Prachtwerte unter seinen Füchsen zu finden.

Heute verlegt der Zwerg einige Füchse in andere Zoos und ersetzt sie durch Füchse, die die anderen Zoos im Gegenzug geschickt haben. Zu Beginn des Tages steht Zwerg der Tierpfleger mit einem Wagen voller neuer Füchse neben dem ersten (am weitesten links gelegenen) Gehege. Der Zwerg geht den Weg entlang und bewegt sich von Gehege zu Gehege. Manchmal hält er an einem der Gehege an und ersetzt den dortigen Fuchs durch einen anderen Fuchs, der möglicherweise einen anderen Prachtwert hat. Jedes Mal, wenn dies geschieht, muss er sofort die Länge der längsten aufsteigenden Prachtwert-Teilfolge berechnen. Kannst du ihm helfen, diese Zahl im Auge zu behalten?

Eingabe

Die erste Zeile der Eingabe enthält zwei ganze Zahlen $N$ und $Q$, welche die Anzahl der Gehege entlang des Weges und die Anzahl der Aktionen des Zwergs darstellen.

Die zweite Zeile der Eingabe enthält $N$ ganze Zahlen $m_1, m_2, \dots, m_N$, welche den anfänglichen Prachtwert jedes Fuchses beschreiben.

Die nächsten $Q$ Zeilen beschreiben die Aktionen. Eine einzelne Aktion ist eine der folgenden:

1. < — der Zwerg bewegt sich um ein Gehege nach links,
2. > — der Zwerg bewegt sich um ein Gehege nach rechts,
3. ! v — der Zwerg tauscht den Fuchs im aktuellen Gehege gegen einen Fuchs mit dem Prachtwert $v$ aus.

Ausgabe

Gib für jede !-Aktion eine einzige Zeile aus, die die Länge der längsten aufsteigenden Teilfolge der Prachtwerte der Füchse enthält.

Einschränkungen

$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$.

Beispiele

Eingabe 1

5 8
3 4 1 7 2
>
! 2
>
>
>
! 10
<
! 11

Ausgabe 1

2
3
2

Hinweis

Zuerst bewegt sich Zwerg der Tierpfleger zum zweiten Gehege und tauscht den Fuchs gegen einen mit dem Prachtwert $2$ aus. Die Länge der längsten aufsteigenden Teilfolge beträgt $2$. Dann bewegt er sich zum fünften Gehege und tauscht den Fuchs gegen einen mit dem Prachtwert $10$ aus, wodurch die Länge der LIS zu $3$ wird. Schließlich bewegt sich der Tierpfleger zum vierten Gehege und ändert den Prachtwert auf $11$, wodurch die Länge der LIS wieder $2$ wird.