El Enano Cuidador del Zoológico ha sido ascendido recientemente a jefe del Pabellón de los Zorros en el Zoológico de Breslavia (Wrocław). Su amor por el zorro (o lis, como se le llama en polaco) no conoce límites.
El enano cuida de una larga fila de zorros en recintos dispuestos a lo largo del camino principal. Cada zorro tiene un valor de magnificencia, y el enano se enorgullece de encontrar la Subsecuencia Creciente Más Larga (LIS) de magnificencia entre sus zorros.
Hoy, el enano está transfiriendo algunos zorros a otros zoológicos y reemplazándolos con zorros que los otros zoológicos enviaron a cambio. Al comienzo del día, el Enano Cuidador del Zoológico se encuentra con un carrito de zorros nuevos junto al primer recinto (el de más a la izquierda). El enano caminará a lo largo del sendero, moviéndose de recinto en recinto. A veces, se detendrá en uno de los recintos y reemplazará al zorro que está allí por otro zorro, posiblemente con una magnificencia diferente. Cada vez que esto sucede, debe calcular inmediatamente la longitud de la subsecuencia creciente de magnificencia más larga. ¿Puedes ayudarlo a llevar el registro de este número?
Entrada
La primera línea de la entrada contiene dos enteros $N$ y $Q$, que representan el número de recintos a lo largo del camino y el número de acciones que realiza el enano.
La segunda línea de la entrada contiene $N$ enteros $m_1, m_2, \dots, m_N$, que describen la magnificencia inicial de cada zorro.
Las siguientes $Q$ líneas describen las acciones. Una sola acción es una de las siguientes:
<— el enano se mueve un recinto hacia la izquierda,>— el enano se mueve un recinto hacia la derecha,! v— el enano cambia el zorro en el recinto actual por un zorro con magnificencia $v$.
Salida
Para cada acción !, imprime una sola línea que contenga la longitud de la subsecuencia creciente más larga de la magnificencia de los zorros.
Límites
$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$.
Ejemplos
Entrada 1
5 8 3 4 1 7 2 > ! 2 > > > ! 10 < ! 11
Salida 1
2 3 2
Nota
Primero, el Enano Cuidador del Zoológico se mueve al segundo recinto y cambia el zorro por uno con magnificencia $2$. La longitud de la subsecuencia creciente más larga es $2$. Luego se mueve al quinto recinto y cambia el zorro por uno con magnificencia $10$, y la longitud de la LIS se convierte en $3$. Finalmente, el Cuidador se mueve al cuarto recinto y cambia la magnificencia a $11$, haciendo que la longitud de la LIS vuelva a ser $2$.