Il mizuyokan è un dolce tradizionale giapponese a base di pasta di fagioli azuki. Si prepara cuocendo la pasta di fagioli azuki con l'agar e facendola solidificare in uno stampo rettangolare.

Ora JOI-kun possiede una macchina per mizuyokan. Usandola, JOI-kun può preparare un mizuyokan di forma rettangolare allungata orizzontalmente con $N-1$ linee di taglio verticali. La lunghezza del mizuyokan e le posizioni delle linee di taglio sono determinate dai $N$ parametri $d_1,d_2,\ldots,d_N$ impostati sulla macchina. La lunghezza del mizuyokan è $d_1+d_2+\cdots+d_N$. La distanza tra la $(i-1)$-esima linea di taglio ($1\le i\le N$) da sinistra e la $i$-esima linea di taglio da sinistra è $d_i$. Qui consideriamo il bordo più a sinistra del mizuyokan come la $0$-esima linea di taglio, e il bordo più a destra del mizuyokan come la $N$-esima linea di taglio. All'inizio, i parametri della macchina per mizuyokan soddisfano $d_i=L_i$ ($1\le i\le N$).

JOI-kun ha in programma di organizzare $Q$ ricevimenti del tè. Il $j$-esimo ricevimento del tè ($1\le j\le Q$) è descritto dagli interi $X_j,Y_j,A_j,B_j$ e si svolge come segue.

1. Il parametro $d_{X_j}$ della macchina per mizuyokan viene aggiornato e impostato a $Y_j$.
2. JOI-kun prepara un nuovo mizuyokan usando la macchina per mizuyokan. Prende la parte del mizuyokan compresa tra la $A_j$-esima linea di taglio e la $B_j$-esima linea di taglio, e la usa per il ricevimento del tè. Mangia il resto.
3. JOI-kun taglia la parte del mizuyokan destinata al ricevimento del tè lungo alcune delle linee di taglio, dividendola in uno o più pezzi. In questo processo deve essere soddisfatta la seguente condizione: ordinando i pezzi da sinistra come nelle posizioni originali, la sequenza delle lunghezze dei pezzi deve essere a zigzag.

Qui, una sequenza è detta a zigzag se i suoi elementi crescono e decrescono alternativamente. Ad esempio, le sequenze $(2,9,2,7)$, $(7,1,9,4,6)$, $(5)$, $(2,1)$ sono a zigzag, ma le sequenze $(1,2,3)$, $(7,1,4,4,6)$, $(2,2)$ non sono a zigzag. Precisamente, una sequenza $(x_1,x_2,\ldots,x_m)$ è detta a zigzag se è soddisfatta almeno una delle seguenti condizioni (o entrambe):

• Per $k=1,2,\ldots,m-1$, vale la disuguaglianza $x_k<x_{k+1}$ se $k$ è dispari, e vale la disuguaglianza $x_k>x_{k+1}$ se $k$ è pari.
• Per $k=1,2,\ldots,m-1$, vale la disuguaglianza $x_k>x_{k+1}$ se $k$ è dispari, e vale la disuguaglianza $x_k<x_{k+1}$ se $k$ è pari.

Poiché JOI-kun vuole offrire il mizuyokan al maggior numero possibile di amici, desidera massimizzare il numero di pezzi ottenuti tramite il passo 3. del ricevimento del tè.

Scrivi un programma che, date le informazioni sui parametri iniziali della macchina per mizuyokan e il programma dei ricevimenti del tè, calcoli per ciascun ricevimento del tè il massimo numero possibile di pezzi ottenibili tagliando la parte di mizuyokan in modo che la condizione sia soddisfatta. Nota che, sotto i vincoli di questo problema, è sempre possibile tagliare la parte di mizuyokan in modo da soddisfare la condizione.

Dati di input

Leggi i seguenti dati dallo standard input.

$$ \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} $$

Dati di output

Scrivi $Q$ righe sullo standard output. La $j$-esima riga ($1\le j\le Q$) dell'output corrisponde al $j$-esimo ricevimento del tè e deve contenere il massimo numero possibile di pezzi ottenibili tagliando la parte di mizuyokan nel $j$-esimo ricevimento del tè in modo che la condizione sia soddisfatta.

Vincoli

• $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$).
• Tutti i valori forniti sono interi.

Subtask

1. (6 punti) $N\le 200,Q\le 10$.
2. (9 punti) $N\le 2\,000,Q\le 10$.
3. (13 punti) $Q\le 10$.
4. (32 punti) $Y_j=L_{X_j}$ ($1\le j\le Q$).
5. (29 punti) $L_i\le 120\,000$ ($1\le i\le N$), $Y_j\le 120\,000$ ($1\le j\le Q$).
6. (11 punti) Nessun vincolo aggiuntivo.

Esempi

Input 1

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

Output 1

3

Note

Nel primo ricevimento del tè, i parametri della macchina per mizuyokan sono impostati a $(d_1,d_2,d_3,d_4,d_5,d_6)=(5,6,8,7,4,9)$. JOI-kun usa la parte del mizuyokan tra la $0$-esima linea di taglio e la $5$-esima linea di taglio, come mostrato nella Figura 1.

Figura 1. Il mizuyokan per il ricevimento del tè

Ad esempio, JOI-kun può tagliare la parte del mizuyokan come segue.

Figura 2. Tre metodi per tagliare il mizuyokan. Dall'alto: Metodo 1, Metodo 2, Metodo 3.

Nel Metodo 1, le lunghezze dei pezzi sono $5,14,7,4$. Poiché questa sequenza non è a zigzag, non soddisfa la condizione. D'altra parte, nel Metodo 2, le lunghezze dei pezzi sono $11,8,11$. Poiché questa sequenza è a zigzag, soddisfa la condizione. Nel Metodo 3, la lunghezza del pezzo è $30$. Poiché questa sequenza è a zigzag, soddisfa anch'essa la condizione.

Se JOI-kun taglia la parte del mizuyokan con il Metodo 2, ottiene 3 pezzi. Poiché non è possibile tagliare la parte del mizuyokan in modo da soddisfare la condizione ottenendo un numero di pezzi maggiore o uguale a 4, stampa 3 nella prima riga.

Questo input di esempio soddisfa i vincoli di tutti i subtask.

Input 2

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

Output 2

1
2
3

Note

Nel primo ricevimento del tè, la lunghezza della parte di mizuyokan per il ricevimento è $4$. C'è una linea di taglio a distanza $2$ dal bordo più a sinistra. Se JOI-kun usa il mizuyokan senza tagliarlo, ottiene un pezzo. La sequenza delle lunghezze dei pezzi è $(4)$, che è a zigzag. Poiché non può ottenere più di un pezzo, stampa 1.

Nel secondo ricevimento del tè, la lunghezza della parte di mizuyokan per il ricevimento è $9$. Ci sono due linee di taglio a distanze $2,4$ dal bordo più a sinistra. Se JOI-kun taglia il mizuyokan lungo la linea di taglio a distanza $4$ dal bordo più a sinistra, ottiene due pezzi. La sequenza delle lunghezze dei pezzi è $(4,5)$, che è a zigzag. Poiché non può ottenere più di due pezzi, stampa 2.

Nel terzo ricevimento del tè, la lunghezza della parte di mizuyokan per il ricevimento è $10$. Ci sono tre linee di taglio a distanze $1,3,5$ dal bordo più a sinistra. Se JOI-kun taglia il mizuyokan lungo le linee di taglio a distanze $3,5$ dal bordo più a sinistra, ottiene tre pezzi. La sequenza delle lunghezze dei pezzi è $(3,2,5)$, che è a zigzag. Poiché non può ottenere più di tre pezzi, stampa 3.

Questo input di esempio soddisfa i vincoli dei Subtask $1,2,3,5,6$.