Descripción

OCI-kun tiene ~N~ peces, numerados de ~1~ a ~N~. El tamaño del pez ~i~ (~1 \le i \le N~) es ~A_i~. Cuando criamos peces, tenemos que prestar atención al siguiente hecho: si tenemos dos peces cercanos, un pez se come a al otro pez a medida que pasa el tiempo. En este caso, dos peces están próximos si no hay ningún pez entre ellos. Más concretamente, si el tamaño del pez ~x~ es mayor o igual que el del pez ~y~, y el pez ~x~ y el pez ~y~ están cerca, entonces el pez ~x~ se come al pez ~y~, y el tamaño de ~x~ se convierte en la suma del tamaño original de ~x~ y el tamaño de ~y~. Si el pez ~x~ y el pez ~y~ tienen el mismo tamaño, cualquiera de ellos puede comerse al otro.

OCI-kun cultivará peces durante ~Q~ días. Para matar el tiempo, hace el siguiente experimento mental. El j-ésimo día (~1 \le j \le Q~), OCI-kun realiza una de las siguientes acciones.

• Tipo 1 : OCI-kun da un alimento especial al pez ~X_j~. Después de eso, el tamaño del pez ~X_j~ se convierte en ~Y_j~.
• Tipo 2 : OCI-kun toma sólo los peces cuyos índices están entre ~L_j~ y ~R_j~, ambos inclusive. Entonces OCI-kun realiza el siguiente experimento mental:

OCI-kun pone los peces ~L_j, L_j + 1, . . . R_j~ en un acuario de izquierda a derecha. Por las propiedades de los peces, sólo sobrevivirá un pez en el acuario. El índice del pez superviviente depende de la elección de los peces comidos y del momento en que un pez se come a otro. OCI-kun quiere saber el número de índices posibles de peces supervivientes. Durante el experimento mental, el orden de los peces no cambia, y no hay dos peces que se coman al mismo pez simultáneamente.

Tarea

Escribe un programa que, dada la información de los peces de OCI-kun y el plan de OCI-kun, calcule el número de posibles índices de peces supervivientes para cada acción del Tipo 2 con el fin de determinar si el pensamiento de OCI-kun es correcto o no. Tenga en cuenta que esto es sólo un experimento mental. Tenga la seguridad de que en realidad no se come ningún pez.

Entrada

Lea los siguientes datos de la entrada estándar. Los valores dados son todos enteros.

~N~

~A_1 A_2 ... A_N~

~Q~

(Consulta ~1~)

(Consulta ~2~)

.

(Consulta ~Q~)

Cada (Consulta ~j~) (~1 \le j \le Q~) consta de números enteros separados por espacios. Sea ~T_j~ el primer entero de (~Consulta j~). El contenido de esta línea es uno de los siguientes.

• Si ~T_j~ = ~1~, esta línea contiene otros dos enteros separados por espacios ~X_j~, ~Y_j~, en este orden. Esto significa que OCI-kun realiza una acción del tipo 1 el día ~j~. El tamaño del pez ~X_j~ se convierte en ~Y_j~.

• Si ~T_j~ = ~2~, esta línea contiene otros dos enteros separados por espacios ~L~ ~j~, ~R_j~, en este orden. Esto significa que OCI-kun realiza una acción de Tipo 2 el día j-ésimo. OCI-kun realiza un experimento mental para los peces cuyos índices están entre ~L_j~ y ~R_j~, ambos inclusive.

Salida

Para cada acción de Tipo 2 (es decir, para cada ~j~ (~1 \le j \le Q~) con ~T_j~ = ~2~), en orden, escriba el número de posibles índices de peces supervivientes en la salida estándar. Las salidas deben estar separadas por saltos de línea.

Restricciones

• ~1 \le N \le 100 000~.
• ~1 \le Q \le 100 000~.
• ~1 \le A_i \le 1 000 000 000 (= 10^9) (1 \le i \le N)~.
• ~T_j~ es ~1~ o ~2~ ~(1 \le j \le Q)~.
• ~1 \le X_j \le N (1 \le j \le Q)~.
• ~1 \le Y_j \le 1 000 000 000 (= 10^9) (1 \le j \le Q)~.
• ~1 \le L_j \le R_j \le N (1 \le j \le Q)~.

Subtareas

1. (5 puntos) ~N \le 500~, ~Q \le 500~.
2. (8 puntos) ~Q = 1~, ~T_j = 2, L_j = 1, R_j = N (1 \le j \le Q)~.
3. (12 puntos) ~Q \le 1 000~.
4. (23 puntos) ~T_j = 2 (1 \le j \le Q)~．
5. (35 puntos) Para cada ~j~ (~1 \le j \le Q~) con ~T_j = 2~, se satisfacen las igualdades ~L_j~ = ~1~ y ~R_j = N~.
6. (17 puntos) No hay restricciones adicionales.

Ejemplos de Entrada y Salida

Ejemplo de Entrada #1

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

Ejemplo de salida #1

5
2
2
3
1

Durante 6 días, OCI-kun realiza las siguientes acciones.

• El primer día, OCI-kun realiza un experimento mental para los peces ~1, 2, 3, 4, 5~.
• El segundo día, OCI-kun realiza un experimento mental para los peces ~1, 2, 3~.
• El tercer día, OCI-kun da un alimento especial al pez 3. Después de eso, el tamaño del pez 3 se convierte en 1.
• El cuarto día, OCI-kun realiza un experimento mental para los peces ~2, 3, 4, 5~.
• El quinto día, OCI-kun realiza un experimento mental para los peces ~1, 2, 3, 4, 5~.
• El sexto día, OCI-kun realiza un experimento mental para los peces ~2, 3, 4...~ Los resultados del experimento mental del primer día son los siguientes.
• Los tamaños de los peces en el acuario son ~6, 4, 2, 2, 6~ de izquierda a derecha.
• Por ejemplo, el ~pez 2~ sobrevive en el acuario mediante el siguiente proceso. (Una matriz especifica los tamaños de los peces del acuario de izquierda a derecha. Un carácter en negrita especifica el tamaño del ~pez 2~.) [~6, 4, 2, 2, 6~]（Estado inicial） → [~6, 4, 4, 6~] El ~pez 4~ se come al ~pez 3~） → [~6, 8, 6~]（El ~pez 2~ se come al ~pez 4~）→ [~14, 6~]（El ~pez 2~ se come al ~pez 1~） → [~20~]（El ~pez 2~ se come al ~pez 5~)
• Del mismo modo, los posibles índices de peces supervivientes son ~1, 2, 3, 4, 5~. Por lo tanto, hay cinco posibilidades.

Este ejemplo de entrada satisface las restricciones de las subtareas ~1, 3, 6~.

Ejemplo de Entrada #2

13
10 4 2 5 20 5 4 8 20 10 3 3 7
1
2 1 13

Ejemplo de Salida #2

7

Este ejemplo de entrada satisface todas las restricciones

Ejemplo de Entrada #3

12
32 32 4 1 1 1 1 4 4 16 32 128
7
2 1 12
2 2 6
2 8 10
2 1 9
2 3 8
2 5 9
2 2 12

Ejemplo de Salida #3

12
1
1
2
6
2
1

Este ejemplo de entrada satisface las restricciones de las subtareas ~1, 3, 4 y 6~.

Ejemplo de Entrada #4

10
2 3 5 10 1 3 4 9 5 2
8
2 1 10
1 10 5
2 1 10
1 4 1000000000
2 1 10
1 8 20
1 4 8
2 1 10

Ejemplo de Salida #4

4
6
1
6

Este ejemplo de entrada satisface las restricciones de las subtareas ~1, 3, 5 y 6~.