El mizuyokan es un dulce japonés hecho de pasta de judías azuki. Se prepara cociendo la pasta de judías azuki con agar y dejándola solidificar en un molde rectangular.

Ahora, JOI-kun tiene una máquina de mizuyokan. Con ella puede preparar un mizuyokan rectangular alargado horizontalmente con $N-1$ líneas de corte verticales. La longitud del mizuyokan y las posiciones de las líneas de corte están determinadas por los $N$ parámetros $d_1,d_2,\ldots,d_N$ configurados en la máquina. La longitud del mizuyokan es $d_1+d_2+\cdots+d_N$. La distancia entre la línea de corte número $i-1$ desde la izquierda ($1\le i\le N$) y la línea de corte número $i$ desde la izquierda es $d_i$. Aquí consideramos el borde izquierdo del mizuyokan como la línea de corte número $0$ y el borde derecho como la línea de corte número $N$. Al principio, los parámetros de la máquina satisfacen $d_i=L_i$ ($1\le i\le N$).

JOI-kun planea organizar $Q$ reuniones para tomar el té. La reunión número $j$ ($1\le j\le Q$) se describe mediante los enteros $X_j,Y_j,A_j,B_j$ y se desarrolla de la siguiente forma.

1. Se actualiza el parámetro $d_{X_j}$ de la máquina de mizuyokan, asignándole el valor $Y_j$.
2. JOI-kun prepara un nuevo mizuyokan con la máquina. Toma la parte comprendida entre las líneas de corte número $A_j$ y número $B_j$ para la reunión, y se come el resto.
3. JOI-kun corta la parte destinada a la reunión por algunas de sus líneas de corte, dividiéndola en una o más porciones. En este proceso debe cumplirse la siguiente condición: al ordenar las porciones de izquierda a derecha según sus posiciones originales, la secuencia de sus longitudes debe ser zigzag.

Una secuencia se llama zigzag si sus elementos aumentan y disminuyen alternadamente. Por ejemplo, las secuencias $(2,9,2,7)$, $(7,1,9,4,6)$, $(5)$ y $(2,1)$ son zigzag, pero las secuencias $(1,2,3)$, $(7,1,4,4,6)$ y $(2,2)$ no lo son. Más precisamente, una secuencia $(x_1,x_2,\ldots,x_m)$ se llama zigzag si satisface una de las siguientes condiciones, o ambas:

• Para $k=1,2,\ldots,m-1$, se cumple $x_k<x_{k+1}$ si $k$ es impar, y $x_k>x_{k+1}$ si $k$ es par.
• Para $k=1,2,\ldots,m-1$, se cumple $x_k>x_{k+1}$ si $k$ es impar, y $x_k<x_{k+1}$ si $k$ es par.

Como JOI-kun quiere dar mizuyokan a tantos amigos como sea posible, desea maximizar el número de porciones obtenidas en el paso 3 de la reunión.

Escribe un programa que, dada la información sobre los parámetros iniciales de la máquina de mizuyokan y el plan de las reuniones, calcule, para cada reunión, el máximo número de porciones que se pueden obtener cortando la parte del mizuyokan de modo que se cumpla la condición. Ten en cuenta que, bajo las restricciones de esta tarea, siempre es posible cortar la parte del mizuyokan de modo que se cumpla la condición.

Entrada

Lee los siguientes datos de la entrada estándar.

$$ \begin{array}{l} N \\ L_1\ L_2\ \cdots\ L_N \\ Q \\ X_1\ Y_1\ A_1\ B_1 \\ X_2\ Y_2\ A_2\ B_2 \\ \vdots \\ X_Q\ Y_Q\ A_Q\ B_Q \end{array} $$

Salida

Escribe $Q$ líneas en la salida estándar. La línea $j$ ($1\le j\le Q$) corresponde a la reunión número $j$ y contiene el máximo número de porciones que se pueden obtener cortando la parte del mizuyokan en esa reunión de modo que se cumpla la condición.

Restricciones

• $1\le N\le 250\,000$.
• $1\le L_i\le 10^9$ ($1\le i\le N$).
• $1\le Q\le 50\,000$.
• $1\le X_j\le N$ ($1\le j\le Q$).
• $1\le Y_j\le 10^9$ ($1\le j\le Q$).
• $0\le A_j<B_j\le N$ ($1\le j\le Q$).
• Todos los valores dados son enteros.

Subtareas

1. (6 puntos) $N\le 200$, $Q\le 10$.
2. (9 puntos) $N\le 2\,000$, $Q\le 10$.
3. (13 puntos) $Q\le 10$.
4. (32 puntos) $Y_j=L_{X_j}$ ($1\le j\le Q$).
5. (29 puntos) $L_i\le 120\,000$ ($1\le i\le N$), $Y_j\le 120\,000$ ($1\le j\le Q$).
6. (11 puntos) No hay restricciones adicionales.

Ejemplos

Entrada 1

6
5 6 8 7 4 9
1
6 9 0 5

Salida 1

3

Nota

En la primera reunión, los parámetros de la máquina son $(d_1,d_2,d_3,d_4,d_5,d_6)=(5,6,8,7,4,9)$. JOI-kun utiliza la parte del mizuyokan comprendida entre las líneas de corte número $0$ y número $5$, como muestra la Figura 1.

Figura 1. El mizuyokan para la reunión

Por ejemplo, JOI-kun puede cortar esa parte del mizuyokan de las siguientes formas.

Figura 2. Tres métodos para cortar el mizuyokan. De arriba abajo: Método 1, Método 2 y Método 3.

En el Método 1, las longitudes de las porciones son $5,14,7,4$. Como esta secuencia no es zigzag, no cumple la condición. En cambio, en el Método 2, las longitudes de las porciones son $11,8,11$. Como esta secuencia es zigzag, cumple la condición. En el Método 3, la longitud de la porción es $30$. Como esta secuencia es zigzag, también cumple la condición.

Si JOI-kun corta esa parte del mizuyokan con el Método 2, obtiene 3 porciones. Como no puede cortarla de manera que se cumpla la condición y obtener 4 porciones o más, imprime 3 en la primera línea.

Esta entrada de ejemplo satisface las restricciones de todas las subtareas.

Entrada 2

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

Salida 2

1
2
3

Nota

En la primera reunión, la longitud de la parte del mizuyokan destinada a la reunión es $4$. Hay una línea de corte a distancia $2$ del borde izquierdo. Si JOI-kun utiliza el mizuyokan sin cortarlo, obtiene una porción. La secuencia de longitudes es $(4)$, que es zigzag. Como no puede obtener más de una porción, imprime 1.

En la segunda reunión, la longitud de la parte del mizuyokan destinada a la reunión es $9$. Hay dos líneas de corte a distancias $2,4$ del borde izquierdo. Si JOI-kun corta el mizuyokan por la línea de corte a distancia $4$ del borde izquierdo, obtiene dos porciones. La secuencia de longitudes es $(4,5)$, que es zigzag. Como no puede obtener más de dos porciones, imprime 2.

En la tercera reunión, la longitud de la parte del mizuyokan destinada a la reunión es $10$. Hay tres líneas de corte a distancias $1,3,5$ del borde izquierdo. Si JOI-kun corta el mizuyokan por las líneas de corte a distancias $3,5$ del borde izquierdo, obtiene tres porciones. La secuencia de longitudes es $(3,2,5)$, que es zigzag. Como no puede obtener más de tres porciones, imprime 3.

Esta entrada de ejemplo satisface las restricciones de las subtareas 1, 2, 3, 5, 6.