Mizuyokan är en japansk sötsak gjord på azukibönpasta. Den tillverkas genom att koka azukibönpasta med agar och låta den stelna i en rektangulär form.

Nu har JOI-kun en mizuyokan-maskin. Med hjälp av den kan JOI-kun göra en horisontellt långsmal, rektangulär mizuyokan med $N-1$ vertikala skärlinjer. Längden på mizuyokanen och skärlinjernas positioner bestäms av de $N$ parametrarna $d_1,d_2,\ldots,d_N$ som är inställda på maskinen. Längden på mizuyokanen är $d_1+d_2+\cdots+d_N$. Avståndet mellan den $(i-1)$:a skärlinjen ($1\le i\le N$) från vänster och den $i$:te skärlinjen från vänster är $d_i$. Här betraktar vi mizuyokanens vänstra kant som den $0$:te skärlinjen och dess högra kant som den $N$:te skärlinjen. Från början uppfyller parametrarna i mizuyokan-maskinen $d_i=L_i$ ($1\le i\le N$).

JOI-kun planerar att anordna $Q$ tebjudningar. Den $j$:te tebjudningen ($1\le j\le Q$) beskrivs av heltalen $X_j,Y_j,A_j,B_j$ och går till på följande sätt.

1. Parametern $d_{X_j}$ i mizuyokan-maskinen uppdateras och sätts till $Y_j$.
2. JOI-kun gör en ny mizuyokan med hjälp av mizuyokan-maskinen. Han tar delen av mizuyokanen mellan den $A_j$:te skärlinjen och den $B_j$:te skärlinjen och använder den till tebjudningen. Resten äter han upp.
3. JOI-kun skär delen av mizuyokanen för tebjudningen längs några av skärlinjerna. Han delar upp denna del i en eller flera bitar. I denna process måste följande villkor vara uppfyllt: om bitarna ordnas från vänster enligt sina ursprungliga positioner ska talföljden av bitarnas längder vara sicksack (zigzag).

Här kallas en talföljd sicksack om elementen i följden växelvis ökar och minskar. Till exempel är talföljderna $(2,9,2,7)$, $(7,1,9,4,6)$, $(5)$, $(2,1)$ sicksack, men talföljderna $(1,2,3)$, $(7,1,4,4,6)$, $(2,2)$ är inte sicksack. Mer precist kallas en talföljd $(x_1,x_2,\ldots,x_m)$ sicksack om ett (eller båda) av följande villkor är uppfyllda:

• För $k=1,2,\ldots,m-1$ gäller olikheten $x_k<x_{k+1}$ om $k$ är udda, och olikheten $x_k>x_{k+1}$ om $k$ är jämnt.
• För $k=1,2,\ldots,m-1$ gäller olikheten $x_k>x_{k+1}$ om $k$ är udda, och olikheten $x_k<x_{k+1}$ om $k$ är jämnt.

Eftersom JOI-kun vill ge mizuyokan till så många vänner som möjligt vill han maximera antalet bitar som erhålls i steg 3. under tebjudningen.

Skriv ett program som, givet information om de ursprungliga parametrarna i mizuyokan-maskinen och planen för tebjudningarna, för varje tebjudning beräknar det maximalt möjliga antalet bitar som kan fås genom att skära delen av mizuyokanen så att villkoret är uppfyllt. Observera att det under begränsningarna för denna uppgift alltid är möjligt att skära delen av mizuyokanen så att villkoret är uppfyllt.

Indata

Läs in följande data från 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} $$

Utdata

Skriv $Q$ rader till standard output. Den $j$:te raden ($1\le j\le Q$) i utdata motsvarar den $j$:te tebjudningen. Den ska innehålla det maximalt möjliga antalet bitar som kan fås genom att skära delen av mizuyokanen under den $j$:te tebjudningen så att villkoret är uppfyllt.

Begränsningar

• $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$).
• Alla givna värden är heltal.

Deluppgifter

1. (6 poäng) $N\le 200,Q\le 10$.
2. (9 poäng) $N\le 2\,000,Q\le 10$.
3. (13 poäng) $Q\le 10$.
4. (32 poäng) $Y_j=L_{X_j}$ ($1\le j\le Q$).
5. (29 poäng) $L_i\le 120\,000$ ($1\le i\le N$), $Y_j\le 120\,000$ ($1\le j\le Q$).
6. (11 poäng) Inga ytterligare begränsningar.

Exempel

Indata 1

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

Utdata 1

3

Förklaring

Under den första tebjudningen är parametrarna i mizuyokan-maskinen inställda på $(d_1,d_2,d_3,d_4,d_5,d_6)=(5,6,8,7,4,9)$. JOI-kun använder delen av mizuyokanen mellan den $0$:te skärlinjen och den $5$:te skärlinjen såsom i Figur 1.

Figur 1. Mizuyokanen till tebjudningen

JOI-kun kan till exempel skära delen av mizuyokanen på följande sätt.

Figur 2. Tre metoder att skära mizuyokanen. Metod 1, Metod 2, Metod 3 uppifrån och ned.

I Metod 1 är bitarnas längder $5,14,7,4$. Eftersom denna talföljd inte är sicksack uppfyller den inte villkoret. Å andra sidan är bitarnas längder i Metod 2 lika med $11,8,11$. Eftersom denna talföljd är sicksack uppfyller den villkoret. I Metod 3 är bitens längd $30$. Eftersom denna talföljd är sicksack uppfyller även den villkoret.

Om JOI-kun skär delen av mizuyokanen enligt Metod 2 får han 3 bitar. Eftersom det inte är möjligt för honom att skära delen av mizuyokanen så att villkoret är uppfyllt och han får minst 4 bitar, skriv ut 3 på första raden.

Detta exempelindata uppfyller begränsningarna för alla deluppgifter.

Indata 2

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

Utdata 2

1
2
3

Förklaring

Under den första tebjudningen är längden på delen av mizuyokanen för tebjudningen $4$. Det finns en skärlinje på avståndet $2$ från den vänstra kanten. Om JOI-kun använder mizuyokanen utan att skära den får han en bit. Talföljden av bitarnas längder är $(4)$, vilket är sicksack. Eftersom han inte kan få fler än en bit, skriv ut 1.

Under den andra tebjudningen är längden på delen av mizuyokanen för tebjudningen $9$. Det finns två skärlinjer på avstånden $2,4$ från den vänstra kanten. Om JOI-kun skär mizuyokanen vid skärlinjen på avståndet $4$ från den vänstra kanten får han två bitar. Talföljden av bitarnas längder är $(4,5)$, vilket är sicksack. Eftersom han inte kan få fler än två bitar, skriv ut 2.

Under den tredje tebjudningen är längden på delen av mizuyokanen för tebjudningen $10$. Det finns tre skärlinjer på avstånden $1,3,5$ från den vänstra kanten. Om JOI-kun skär mizuyokanen vid skärlinjerna på avstånden $3,5$ från den vänstra kanten får han tre bitar. Talföljden av bitarnas längder är $(3,2,5)$, vilket är sicksack. Eftersom han inte kan få fler än tre bitar, skriv ut 3.

Detta exempelindata uppfyller begränsningarna för deluppgifterna $1,2,3,5,6$.