Mizuyokan ist eine japanische Süßigkeit aus Azukibohnenpaste. Sie wird hergestellt, indem man Azukibohnenpaste mit Agar kocht und in einer rechteckigen Form fest werden lässt.

JOI-kun besitzt nun eine Mizuyokan-Maschine. Mit ihr kann er einen waagerecht langen, rechteckigen Mizuyokan mit $N-1$ senkrechten Schnittlinien herstellen. Die Länge des Mizuyokan und die Positionen der Schnittlinien werden durch die $N$ Maschinenparameter $d_1,d_2,\ldots,d_N$ bestimmt. Die Länge des Mizuyokan beträgt $d_1+d_2+\cdots+d_N$. Der Abstand zwischen der $(i-1)$-ten Schnittlinie von links ($1 \le i \le N$) und der $i$-ten Schnittlinie von links beträgt $d_i$. Dabei betrachten wir den linken Rand des Mizuyokan als Schnittlinie $0$ und den rechten Rand als Schnittlinie $N$. Anfangs gelten für die Maschinenparameter $d_i=L_i$ ($1 \le i \le N$).

JOI-kun plant $Q$ Teegesellschaften. Die $j$-te Teegesellschaft ($1 \le j \le Q$) wird durch die ganzen Zahlen $X_j,Y_j,A_j,B_j$ beschrieben und läuft folgendermaßen ab.

1. Der Maschinenparameter $d_{X_j}$ wird aktualisiert und auf $Y_j$ gesetzt.
2. JOI-kun stellt mit der Maschine einen neuen Mizuyokan her. Den Teil zwischen der $A_j$-ten und der $B_j$-ten Schnittlinie verwendet er für die Teegesellschaft. Den Rest isst er selbst.
3. JOI-kun schneidet den für die Teegesellschaft bestimmten Teil entlang einiger Schnittlinien in ein oder mehrere Stücke. Dabei muss folgende Bedingung erfüllt sein: Ordnet man die Stücke entsprechend ihren ursprünglichen Positionen von links nach rechts, so muss die Folge ihrer Längen eine Zickzackfolge sein.

Eine Folge heißt Zickzackfolge, wenn ihre Elemente abwechselnd größer und kleiner werden. Beispielsweise sind $(2,9,2,7)$, $(7,1,9,4,6)$, $(5)$ und $(2,1)$ Zickzackfolgen, während $(1,2,3)$, $(7,1,4,4,6)$ und $(2,2)$ keine sind. Genauer heißt eine Folge $(x_1,x_2,\ldots,x_m)$ Zickzackfolge, wenn eine der folgenden Bedingungen oder beide erfüllt sind:

• Für $k=1,2,\ldots,m-1$ gilt $x_k<x_{k+1}$, wenn $k$ ungerade ist, und $x_k>x_{k+1}$, wenn $k$ gerade ist.
• Für $k=1,2,\ldots,m-1$ gilt $x_k>x_{k+1}$, wenn $k$ ungerade ist, und $x_k<x_{k+1}$, wenn $k$ gerade ist.

Da JOI-kun möglichst vielen Freunden Mizuyokan geben möchte, will er die Anzahl der Stücke maximieren, die in Schritt 3 der Teegesellschaft entstehen.

Schreibe ein Programm, das anhand der anfänglichen Maschinenparameter und des Plans der Teegesellschaften für jede Teegesellschaft die größtmögliche Anzahl an Stücken berechnet, in die sich der betreffende Teil des Mizuyokan unter Einhaltung der Bedingung schneiden lässt. Beachte, dass es unter den Beschränkungen dieser Aufgabe stets möglich ist, den Teil des Mizuyokan so zu schneiden, dass die Bedingung erfüllt ist.

Eingabe

Lies die folgenden Daten von der Standardeingabe ein.

$$ \begin{array}{c} 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} $$

Ausgabe

Gib $Q$ Zeilen auf der Standardausgabe aus. Die $j$-te Ausgabezeile ($1 \le j \le Q$) entspricht der $j$-ten Teegesellschaft und enthält die größtmögliche Anzahl an Stücken, in die sich der betreffende Teil des Mizuyokan bei dieser Teegesellschaft unter Einhaltung der Bedingung schneiden lässt.

Beschränkungen

• $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$).
• Alle gegebenen Werte sind ganze Zahlen.

Teilaufgaben

1. (6 Punkte) $N \le 200$, $Q \le 10$.
2. (9 Punkte) $N \le 2\,000$, $Q \le 10$.
3. (13 Punkte) $Q \le 10$.
4. (32 Punkte) $Y_j=L_{X_j}$ ($1 \le j \le Q$).
5. (29 Punkte) $L_i \le 120\,000$ ($1 \le i \le N$), $Y_j \le 120\,000$ ($1 \le j \le Q$).
6. (11 Punkte) Es gibt keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

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

Ausgabe 1

3

Hinweis

Bei der ersten Teegesellschaft sind die Maschinenparameter auf $(d_1,d_2,d_3,d_4,d_5,d_6)=(5,6,8,7,4,9)$ gesetzt. JOI-kun verwendet den Teil des Mizuyokan zwischen Schnittlinie $0$ und Schnittlinie $5$, wie in Abbildung 1.

Abbildung 1. Der Mizuyokan für die Teegesellschaft

Beispielsweise kann JOI-kun diesen Teil des Mizuyokan folgendermaßen schneiden.

Abbildung 2. Drei Methoden, den Mizuyokan zu schneiden. Von oben nach unten: Methode 1, Methode 2, Methode 3.

Bei Methode 1 haben die Stücke die Längen $5,14,7,4$. Da diese Folge keine Zickzackfolge ist, erfüllt sie die Bedingung nicht. Bei Methode 2 haben die Stücke dagegen die Längen $11,8,11$. Diese Folge ist eine Zickzackfolge und erfüllt die Bedingung. Bei Methode 3 hat das einzige Stück die Länge 30. Da diese Folge eine Zickzackfolge ist, erfüllt sie ebenfalls die Bedingung.

Wenn JOI-kun den Teil des Mizuyokan mit Methode 2 schneidet, erhält er 3 Stücke. Da er ihn nicht so schneiden kann, dass die Bedingung erfüllt ist und mindestens 4 Stücke entstehen, gib in der ersten Zeile 3 aus.

Diese Beispieleingabe erfüllt die Beschränkungen aller Teilaufgaben.

Eingabe 2

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

Ausgabe 2

1
2
3

Hinweis

Bei der ersten Teegesellschaft hat der verwendete Teil des Mizuyokan die Länge 4. Eine Schnittlinie liegt im Abstand 2 vom linken Rand. Verwendet JOI-kun den Mizuyokan ohne weiteren Schnitt, erhält er ein Stück. Die Längenfolge ist $(4)$ und somit eine Zickzackfolge. Da er nicht mehr als ein Stück erhalten kann, gib 1 aus.

Bei der zweiten Teegesellschaft hat der verwendete Teil des Mizuyokan die Länge 9. Zwei Schnittlinien liegen in den Abständen $2,4$ vom linken Rand. Schneidet JOI-kun an der Schnittlinie im Abstand 4 vom linken Rand, erhält er zwei Stücke. Die Längenfolge ist $(4,5)$ und somit eine Zickzackfolge. Da er nicht mehr als zwei Stücke erhalten kann, gib 2 aus.

Bei der dritten Teegesellschaft hat der verwendete Teil des Mizuyokan die Länge 10. Drei Schnittlinien liegen in den Abständen $1,3,5$ vom linken Rand. Schneidet JOI-kun an den Schnittlinien in den Abständen $3,5$ vom linken Rand, erhält er drei Stücke. Die Längenfolge ist $(3,2,5)$ und somit eine Zickzackfolge. Da er nicht mehr als drei Stücke erhalten kann, gib 3 aus.

Diese Beispieleingabe erfüllt die Beschränkungen der Teilaufgaben 1, 2, 3, 5, 6.