¿Conoces la empresa Just Odd Inventions? Su actividad consiste en hacer «inventos simplemente extraños». En lo sucesivo la llamaremos JOI.

Para ampliar su negocio, JOI ha decidido contratar nuevos empleados.

Hay $N$ candidatos. Están numerados del $1$ al $N$, y cada candidato tiene asignado un entero llamado valoración.

En esta contratación se aceptará a todos los candidatos cuya valoración sea mayor o igual que cierto valor. Los nuevos empleados se dividirán en varios grupos. Estos grupos se formarán de manera que se cumpla la siguiente condición:

• Si se contrata tanto al candidato $a$ como al candidato $b$ ($a<b$), estos empleados estarán en el mismo grupo si y solo si se contrata a todos los candidatos $c$ con $a \le c \le b$.

Como responsable de recursos humanos de JOI, debes estimar el número de grupos que se formarán en esta contratación procesando un total de $M$ consultas en orden. La $j$-ésima consulta es de uno de los dos tipos siguientes:

• Calcular el número de grupos que se formarán si se contrata a todos los candidatos cuya valoración sea mayor o igual que $B_j$. Este tipo se denomina consulta de respuesta.
• Actualizar la valoración del candidato $C_j$ a $D_j$. Este tipo se denomina consulta de actualización.

Tarea

Dada la información de las $M$ consultas, escribe un programa que calcule el número de grupos para cada consulta de respuesta.

Entrada

Lee los siguientes datos de la entrada estándar.

• La primera línea contiene los enteros $N,M$, separados por un espacio. Esto indica que hay $N$ candidatos y que debes procesar $M$ consultas.
• La $i$-ésima línea ($1 \le i \le N$) de las siguientes $N$ líneas contiene un entero $A_i$. Esto indica que, antes de procesar las consultas, la valoración del candidato $i$ es $A_i$.

• La $j$-ésima línea ($1 \le j \le M$) de las siguientes $M$ líneas contiene 2 o 3 enteros separados por espacios. Sea $T_j$ el primer entero; el contenido de la línea es uno de los siguientes:

  1. Si $T_j=1$, la línea contiene los enteros $T_j,B_j$, separados por un espacio. Esto indica que la $j$-ésima consulta es una consulta de respuesta que pide el número de grupos que se formarán si se contrata a todos los candidatos cuya valoración sea mayor o igual que $B_j$.
  2. Si $T_j=2$, la línea contiene los enteros $T_j,C_j,D_j$, separados por espacios. Esto indica que la $j$-ésima consulta es una consulta de actualización que cambia la valoración del candidato $C_j$ a $D_j$.

Salida

Escribe en la salida estándar, en orden y en una línea por consulta, el número de grupos correspondiente a cada consulta de respuesta.

Restricciones

Todos los datos de entrada cumplen las siguientes condiciones.

• $1 \le N \le 200\,000$.
• $1 \le M \le 200\,000$.
• $1 \le A_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $1 \le T_j \le 2$ ($1 \le j \le M$).
• $1 \le B_j \le 1\,000\,000\,000$ ($1 \le j \le M$).
• $1 \le C_j \le N$ ($1 \le j \le M$).
• $1 \le D_j \le 1\,000\,000\,000$ ($1 \le j \le M$).
• Existe al menos un $j$ ($1 \le j \le M$) tal que $T_j=1$.

Subtareas

Subtarea 1 [10 puntos]

Se cumplen las siguientes condiciones.

• $N \le 2\,000$.
• $M \le 2\,000$.

Subtarea 2 [30 puntos]

• Se cumple $T_j=1$ ($1 \le j \le M$).

Subtarea 3 [60 puntos]

No hay restricciones adicionales.

Ejemplos

Entrada 1

5 4
8
6
3
5
4
1 5
2 4 1
1 5
1 3

Salida 1

2
1
2

Nota

1. La primera consulta es una consulta de respuesta. Al contratar a los candidatos $1,2,4$, cuyas valoraciones son al menos $5$, se forman dos grupos: uno con los candidatos $1$ y $2$, y otro con el candidato $4$. Por tanto, se escribe $2$.
2. La segunda consulta es una consulta de actualización. La valoración del candidato $4$ se actualiza a $1$.
3. La tercera consulta es una consulta de respuesta. Al contratar a los candidatos $1$ y $2$, cuyas valoraciones son al menos $5$, se forma un único grupo con los candidatos $1$ y $2$. Por tanto, se escribe $1$.
4. La cuarta consulta es una consulta de respuesta. Al contratar a los candidatos $1,2,3,5$, cuyas valoraciones son al menos $3$, se forman dos grupos: uno con los candidatos $1,2,3$, y otro con el candidato $5$. Por tanto, se escribe $2$.

Entrada 2

7 5
13
19
1
15
13
1
19
1 20
1 1
1 6
1 11
1 17

Salida 2

0
1
3
3
2

Nota

El segundo ejemplo cumple las restricciones de la subtarea 2.

Entrada 3

10 5
8
10
15
2
2
8
5
12
11
4
1 5
2 8 4
1 12
2 5 11
1 16

Salida 3

2
1
0