Mizuyokan er en japansk konfekt laget av azukibønnepasta. Den lages ved å koke azukibønnepasta med agar og la den stivne i en rektangulær form.

Nå har JOI-kun en mizuyokan-maskin. Ved å bruke den kan JOI-kun lage en horisontalt avlang, rektangulær mizuyokan med $N-1$ vertikale kuttlinjer. Lengden på mizuyokanen og posisjonene til kuttlinjene bestemmes av de $N$ parameterne $d_1,d_2,\ldots,d_N$ som er stilt inn på maskinen. Lengden på mizuyokanen er $d_1+d_2+\cdots+d_N$. Avstanden mellom den $(i-1)$-te kuttlinjen ($1\le i\le N$) fra venstre og den $i$-te kuttlinjen fra venstre er $d_i$. Her betrakter vi den venstre kanten av mizuyokanen som den $0$-te kuttlinjen, og den høyre kanten av mizuyokanen som den $N$-te kuttlinjen. I starten tilfredsstiller parameterne på mizuyokan-maskinen $d_i=L_i$ ($1\le i\le N$).

JOI-kun planlegger å arrangere $Q$ teselskaper. Det $j$-te teselskapet ($1\le j\le Q$) beskrives av heltallene $X_j,Y_j,A_j,B_j$, og foregår slik:

1. Parameteren $d_{X_j}$ på mizuyokan-maskinen oppdateres og settes til $Y_j$.
2. JOI-kun lager en ny mizuyokan ved hjelp av mizuyokan-maskinen. Han tar delen av mizuyokanen mellom den $A_j$-te kuttlinjen og den $B_j$-te kuttlinjen, og bruker den til teselskapet. Han spiser resten.
3. JOI-kun skjærer opp delen av mizuyokanen til teselskapet langs noen av kuttlinjene. Han deler denne delen opp i ett eller flere stykker. I denne prosessen må følgende betingelse være oppfylt: hvis stykkene ordnes fra venstre som i sine opprinnelige posisjoner, skal følgen av lengdene på stykkene være sikksakk (zigzag).

Her kalles en følge sikksakk dersom elementene i følgen vekselvis øker og minker. For eksempel er følgene $(2,9,2,7)$, $(7,1,9,4,6)$, $(5)$, $(2,1)$ sikksakk, mens følgene $(1,2,3)$, $(7,1,4,4,6)$, $(2,2)$ ikke er sikksakk. Mer presist kalles en følge $(x_1,x_2,\ldots,x_m)$ sikksakk hvis én av (eller begge) de følgende betingelsene er oppfylt:

• For $k=1,2,\ldots,m-1$ gjelder ulikheten $x_k<x_{k+1}$ hvis $k$ er odde, og ulikheten $x_k>x_{k+1}$ hvis $k$ er jevn.
• For $k=1,2,\ldots,m-1$ gjelder ulikheten $x_k>x_{k+1}$ hvis $k$ er odde, og ulikheten $x_k<x_{k+1}$ hvis $k$ er jevn.

Siden JOI-kun ønsker å gi mizuyokan til så mange venner som mulig, vil han maksimere antallet stykker som oppnås i prosedyre 3. i teselskapet.

Skriv et program som, gitt informasjon om startparameterne til mizuyokan-maskinen og planen for teselskapene, for hvert teselskap beregner det maksimalt mulige antallet stykker man kan få ved å skjære opp delen av mizuyokanen slik at betingelsen er oppfylt. Merk at under begrensningene i denne oppgaven er det alltid mulig å skjære opp delen av mizuyokanen slik at betingelsen er oppfylt.

Inndata

Les følgende data fra standard inndata.

$$ \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$ linjer til standard utdata. Den $j$-te linjen ($1\le j\le Q$) av utdata tilsvarer det $j$-te teselskapet. Den skal inneholde det maksimalt mulige antallet stykker som kan oppnås ved å skjære opp delen av mizuyokanen i det $j$-te teselskapet slik at betingelsen er oppfylt.

Begrensninger

• $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 oppgitte verdier er heltall.

Deloppgaver

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

Eksempler

Inndata 1

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

Utdata 1

3

Forklaring

I det første teselskapet settes parameterne til mizuyokan-maskinen til $(d_1,d_2,d_3,d_4,d_5,d_6)=(5,6,8,7,4,9)$. JOI-kun bruker delen av mizuyokanen mellom den $0$-te kuttlinjen og den $5$-te kuttlinjen, som vist i Figur 1.

Figur 1. Mizuyokanen til teselskapet

JOI-kun kan for eksempel skjære opp delen av mizuyokanen slik:

Figur 2. Tre metoder for å skjære mizuyokanen. Metode 1, Metode 2, Metode 3 ovenfra.

I Metode 1 er lengdene på stykkene $5,14,7,4$. Siden denne følgen ikke er sikksakk, tilfredsstiller den ikke betingelsen. Derimot er lengdene på stykkene i Metode 2 lik $11,8,11$. Siden denne følgen er sikksakk, tilfredsstiller den betingelsen. I Metode 3 er lengden på stykket $30$. Siden denne følgen er sikksakk, tilfredsstiller også den betingelsen.

Hvis JOI-kun skjærer opp delen av mizuyokanen med Metode 2, får han 3 stykker. Siden det ikke er mulig for ham å skjære opp delen av mizuyokanen slik at betingelsen er oppfylt og han får større enn eller lik 4 stykker, skrives 3 ut på første linje.

disse eksempeldataene tilfredsstiller begrensningene i alle deloppgavene.

Inndata 2

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

Utdata 2

1
2
3

Forklaring

I det første teselskapet er lengden på delen av mizuyokanen til teselskapet $4$. Det er én kuttlinje med avstand $2$ fra venstre kant. Hvis JOI-kun bruker mizuyokanen uten å skjære i den, får han ett stykke. Følgen av lengdene på stykkene er $(4)$, som er sikksakk. Siden han ikke kan få mer enn ett stykke, skrives 1 ut.

I det andre teselskapet er lengden på delen av mizuyokanen til teselskapet $9$. Det er to kuttlinjer med avstandene $2,4$ fra venstre kant. Hvis JOI-kun skjærer mizuyokanen ved kuttlinjen med avstand $4$ fra venstre kant, får han to stykker. Følgen av lengdene på stykkene er $(4,5)$, som er sikksakk. Siden han ikke kan få mer enn to stykker, skrives 2 ut.

I det tredje teselskapet er lengden på delen av mizuyokanen til teselskapet $10$. Det er tre kuttlinjer med avstandene $1,3,5$ fra venstre kant. Hvis JOI-kun skjærer mizuyokanen ved kuttlinjene med avstandene $3,5$ fra venstre kant, får han tre stykker. Følgen av lengdene på stykkene er $(3,2,5)$, som er sikksakk. Siden han ikke kan få mer enn tre stykker, skrives 3 ut.

Disse eksempeldataene tilfredsstiller begrensningene i deloppgavene $1,2,3,5,6$.