Le mizuyokan est une confiserie japonaise à base de pâte de haricots azuki. On le prépare en cuisant la pâte de haricots azuki avec de l'agar-agar, puis en laissant le mélange se solidifier dans un moule rectangulaire.

JOI-kun possède maintenant une machine à mizuyokan. Elle lui permet de fabriquer un mizuyokan rectangulaire allongé horizontalement, comportant $N-1$ lignes de découpe verticales. La longueur du mizuyokan et les positions des lignes de découpe sont déterminées par les $N$ paramètres $d_1,d_2,\ldots,d_N$ réglés sur la machine. La longueur du mizuyokan est $d_1+d_2+\cdots+d_N$. La distance entre la $(i-1)$-ième ligne de découpe ($1\le i\le N$) en partant de la gauche et la $i$-ième ligne de découpe en partant de la gauche est $d_i$. On considère ici le bord gauche du mizuyokan comme la ligne de découpe d'indice $0$, et son bord droit comme la ligne de découpe d'indice $N$. Initialement, les paramètres de la machine à mizuyokan vérifient $d_i=L_i$ ($1\le i\le N$).

JOI-kun prévoit d'organiser $Q$ goûters. Le $j$-ième goûter ($1\le j\le Q$) est décrit par les entiers $X_j,Y_j,A_j,B_j$. Il se déroule comme suit.

1. Le paramètre $d_{X_j}$ de la machine à mizuyokan est mis à jour et prend la valeur $Y_j$.
2. JOI-kun fabrique un nouveau mizuyokan avec la machine. Il prend la partie du mizuyokan comprise entre les lignes de découpe d'indices $A_j$ et $B_j$ et l'utilise pour le goûter. Il mange le reste.
3. JOI-kun découpe la partie du mizuyokan destinée au goûter le long de certaines lignes de découpe. Il la découpe en un ou plusieurs morceaux. La condition suivante doit être satisfaite : si les morceaux sont ordonnés de gauche à droite selon leurs positions initiales, la suite des longueurs des morceaux est en zigzag.

Une suite est dite en zigzag si ses éléments augmentent et diminuent alternativement. Par exemple, les suites $(2,9,2,7)$, $(7,1,9,4,6)$, $(5)$, $(2,1)$ sont en zigzag, tandis que les suites $(1,2,3)$, $(7,1,4,4,6)$, $(2,2)$ ne le sont pas. Plus précisément, une suite $(x_1,x_2,\ldots,x_m)$ est dite en zigzag si l'une au moins des deux conditions suivantes est satisfaite :

• Pour $k=1,2,\ldots,m-1$, l'inégalité $x_k<x_{k+1}$ est satisfaite si $k$ est impair, et l'inégalité $x_k>x_{k+1}$ est satisfaite si $k$ est pair.
• Pour $k=1,2,\ldots,m-1$, l'inégalité $x_k>x_{k+1}$ est satisfaite si $k$ est impair, et l'inégalité $x_k<x_{k+1}$ est satisfaite si $k$ est pair.

Puisque JOI-kun souhaite offrir du mizuyokan à autant d'amis que possible, il veut maximiser le nombre de morceaux obtenus à l'étape 3 du goûter.

Écrivez un programme qui, étant donné les paramètres initiaux de la machine à mizuyokan et le programme des goûters, calcule pour chaque goûter le nombre maximal de morceaux pouvant être obtenus en découpant la partie du mizuyokan de manière à satisfaire la condition. Notez qu'avec les contraintes de ce problème, il est toujours possible de découper la partie du mizuyokan en satisfaisant la condition.

Entrée

Lisez les données suivantes sur l'entrée standard.

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

Sortie

Écrivez $Q$ lignes sur la sortie standard. La $j$-ième ligne ($1\le j\le Q$) correspond au $j$-ième goûter. Elle contient le nombre maximal de morceaux pouvant être obtenus en découpant la partie du mizuyokan lors du $j$-ième goûter de manière à satisfaire la condition.

Contraintes

• $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$).
• Toutes les valeurs données sont des entiers.

Sous-tâches

1. (6 points) $N\le 200,Q\le 10$.
2. (9 points) $N\le 2\,000,Q\le 10$.
3. (13 points) $Q\le 10$.
4. (32 points) $Y_j=L_{X_j}$ ($1\le j\le Q$).
5. (29 points) $L_i\le 120\,000$ ($1\le i\le N$), $Y_j\le 120\,000$ ($1\le j\le Q$).
6. (11 points) Aucune contrainte supplémentaire.

Exemples

Entrée 1

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

Sortie 1

3

Remarque

Lors du premier goûter, les paramètres de la machine à mizuyokan sont $(d_1,d_2,d_3,d_4,d_5,d_6)=(5,6,8,7,4,9)$. JOI-kun utilise la partie du mizuyokan comprise entre les lignes de découpe d'indices $0$ et $5$, comme dans la figure 1.

Figure 1. Le mizuyokan destiné au goûter

Par exemple, JOI-kun peut découper cette partie du mizuyokan comme suit.

Figure 2. Trois méthodes de découpe du mizuyokan. De haut en bas : méthode 1, méthode 2, méthode 3.

Dans la méthode 1, les longueurs des morceaux sont $5,14,7,4$. Cette suite n'étant pas en zigzag, elle ne satisfait pas la condition. En revanche, dans la méthode 2, les longueurs des morceaux sont $11,8,11$. Cette suite étant en zigzag, elle satisfait la condition. Dans la méthode 3, la longueur du morceau est $30$. Cette suite étant en zigzag, elle satisfait également la condition.

Si JOI-kun découpe la partie du mizuyokan selon la méthode 2, il obtient 3 morceaux. Puisqu'il n'est pas possible de découper cette partie en satisfaisant la condition tout en obtenant au moins 4 morceaux, affichez 3 sur la première ligne.

Cet exemple d'entrée satisfait les contraintes de toutes les sous-tâches.

Entrée 2

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

Sortie 2

1
2
3

Remarque

Lors du premier goûter, la longueur de la partie du mizuyokan destinée au goûter est $4$. Une ligne de découpe se trouve à une distance de $2$ du bord gauche. Si JOI-kun utilise le mizuyokan sans le découper, il obtient un morceau. La suite des longueurs des morceaux est $(4)$, qui est en zigzag. Puisqu'il ne peut pas obtenir plus d'un morceau, affichez 1.

Lors du deuxième goûter, la longueur de la partie du mizuyokan destinée au goûter est $9$. Deux lignes de découpe se trouvent à des distances de $2,4$ du bord gauche. Si JOI-kun découpe le mizuyokan à la ligne située à une distance de $4$ du bord gauche, il obtient deux morceaux. La suite des longueurs des morceaux est $(4,5)$, qui est en zigzag. Puisqu'il ne peut pas obtenir plus de deux morceaux, affichez 2.

Lors du troisième goûter, la longueur de la partie du mizuyokan destinée au goûter est $10$. Trois lignes de découpe se trouvent à des distances de $1,3,5$ du bord gauche. Si JOI-kun découpe le mizuyokan aux lignes situées à des distances de $3,5$ du bord gauche, il obtient trois morceaux. La suite des longueurs des morceaux est $(3,2,5)$, qui est en zigzag. Puisqu'il ne peut pas obtenir plus de trois morceaux, affichez 3.

Cet exemple d'entrée satisfait les contraintes des sous-tâches $1,2,3,5,6$.