Mizuyokan to japoński wyrób cukierniczy z pasty z fasoli azuki. Przygotowuje się go, gotując pastę z fasoli azuki z agarem, a następnie pozostawiając do zastygnięcia w prostokątnej formie.

JOI-kun ma teraz maszynę do mizuyokan. Za jej pomocą może przygotować długi w poziomie prostokątny mizuyokan z $N-1$ pionowymi liniami cięcia. Długość mizuyokan i położenia linii cięcia są wyznaczane przez $N$ parametrów $d_1,d_2,\ldots,d_N$ ustawionych w maszynie. Długość mizuyokan wynosi $d_1+d_2+\cdots+d_N$. Odległość między $(i-1)$-szą linią cięcia ($1 \le i \le N$) od lewej a $i$-tą linią cięcia od lewej wynosi $d_i$. Przyjmujemy, że lewy skraj mizuyokan jest linią cięcia numer $0$, a prawy skraj jest linią cięcia numer $N$. Początkowo parametry maszyny spełniają $d_i=L_i$ ($1 \le i \le N$).

JOI-kun planuje zorganizować $Q$ spotkań przy herbacie. $j$-te spotkanie ($1 \le j \le Q$) opisują liczby całkowite $X_j,Y_j,A_j,B_j$. Przebiega ono następująco.

1. Parametr $d_{X_j}$ maszyny do mizuyokan zostaje zmieniony na $Y_j$.
2. JOI-kun przygotowuje nowy mizuyokan za pomocą maszyny. Bierze część pomiędzy $A_j$-tą a $B_j$-tą linią cięcia i przeznacza ją na spotkanie. Resztę zjada.
3. JOI-kun tnie część mizuyokan przeznaczoną na spotkanie wzdłuż niektórych linii cięcia. Dzieli ją na co najmniej jeden kawałek. Musi przy tym spełnić następujący warunek: jeśli kawałki ustawimy od lewej zgodnie z ich pierwotnymi pozycjami, ciąg ich długości będzie zygzakowaty.

Ciąg nazywamy zygzakowatym, jeśli jego elementy na przemian rosną i maleją. Na przykład ciągi $(2,9,2,7)$, $(7,1,9,4,6)$, $(5)$, $(2,1)$ są zygzakowate, ale ciągi $(1,2,3)$, $(7,1,4,4,6)$, $(2,2)$ nie są zygzakowate. Dokładniej, ciąg $(x_1,x_2,\ldots,x_m)$ nazywamy zygzakowatym, jeśli spełnia co najmniej jeden z następujących warunków:

• Dla $k=1,2,\ldots,m-1$ zachodzi $x_k<x_{k+1}$, gdy $k$ jest nieparzyste, oraz $x_k>x_{k+1}$, gdy $k$ jest parzyste.
• Dla $k=1,2,\ldots,m-1$ zachodzi $x_k>x_{k+1}$, gdy $k$ jest nieparzyste, oraz $x_k<x_{k+1}$, gdy $k$ jest parzyste.

Ponieważ JOI-kun chce poczęstować mizuyokan jak najwięcej przyjaciół, chce zmaksymalizować liczbę kawałków otrzymanych w kroku 3 spotkania.

Napisz program, który na podstawie początkowych parametrów maszyny do mizuyokan i planu spotkań obliczy dla każdego spotkania największą możliwą liczbę kawałków otrzymanych po podzieleniu przeznaczonej na nie części mizuyokan tak, aby warunek był spełniony. Zauważ, że przy ograniczeniach tego zadania zawsze można podzielić tę część mizuyokan tak, aby spełnić warunek.

Wejście

Wczytaj następujące dane ze standardowego wejścia.

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

Wyjście

Wypisz $Q$ wierszy na standardowe wyjście. $j$-ty wiersz ($1 \le j \le Q$) odpowiada $j$-temu spotkaniu. Powinien zawierać największą możliwą liczbę kawałków otrzymanych po podzieleniu części mizuyokan na $j$-tym spotkaniu tak, aby warunek był spełniony.

Ograniczenia

• $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$).
• Wszystkie podane wartości są liczbami całkowitymi.

Podzadania

1. (6 punktów) $N \le 200$, $Q \le 10$.
2. (9 punktów) $N \le 2\,000$, $Q \le 10$.
3. (13 punktów) $Q \le 10$.
4. (32 punkty) $Y_j=L_{X_j}$ ($1 \le j \le Q$).
5. (29 punktów) $L_i \le 120\,000$ ($1 \le i \le N$), $Y_j \le 120\,000$ ($1 \le j \le Q$).
6. (11 punktów) Brak dodatkowych ograniczeń.

Przykład

Wejście 1

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

Wyjście 1

3

Uwagi

Na pierwszym spotkaniu parametry maszyny do mizuyokan są ustawione na $(d_1,d_2,d_3,d_4,d_5,d_6)=(5,6,8,7,4,9)$. JOI-kun wykorzystuje część mizuyokan pomiędzy linią cięcia numer $0$ a linią cięcia numer $5$, jak na rysunku 1.

Rysunek 1. Mizuyokan na spotkanie przy herbacie

Na przykład JOI-kun może podzielić tę część mizuyokan w następujący sposób.

Rysunek 2. Trzy sposoby podziału mizuyokan. Od góry: sposób 1, sposób 2, sposób 3.

W sposobie 1 długości kawałków wynoszą $5,14,7,4$. Ponieważ ciąg ten nie jest zygzakowaty, nie spełnia warunku. Natomiast w sposobie 2 długości kawałków wynoszą $11,8,11$. Ponieważ ten ciąg jest zygzakowaty, spełnia warunek. W sposobie 3 długość kawałka wynosi $30$. Ponieważ ten ciąg jest zygzakowaty, również spełnia warunek.

Jeśli JOI-kun podzieli tę część mizuyokan sposobem 2, otrzyma $3$ kawałki. Ponieważ nie można podzielić tej części mizuyokan tak, aby warunek był spełniony i otrzymać co najmniej $4$ kawałki, wypisz $3$ w pierwszym wierszu.

Ten przykład wejścia spełnia ograniczenia wszystkich podzadań.

Wejście 2

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

Wyjście 2

1
2
3

Uwagi

Na pierwszym spotkaniu długość części mizuyokan przeznaczonej na spotkanie wynosi $4$. Istnieje linia cięcia w odległości $2$ od lewego skraju. Jeśli JOI-kun wykorzysta mizuyokan bez dzielenia go, otrzyma jeden kawałek. Ciąg długości kawałków to $(4)$ i jest zygzakowaty. Ponieważ nie można otrzymać więcej niż jednego kawałka, wypisz $1$.

Na drugim spotkaniu długość części mizuyokan przeznaczonej na spotkanie wynosi $9$. Istnieją dwie linie cięcia w odległościach $2,4$ od lewego skraju. Jeśli JOI-kun przetnie mizuyokan wzdłuż linii w odległości $4$ od lewego skraju, otrzyma dwa kawałki. Ciąg długości kawałków to $(4,5)$ i jest zygzakowaty. Ponieważ nie można otrzymać więcej niż dwóch kawałków, wypisz $2$.

Na trzecim spotkaniu długość części mizuyokan przeznaczonej na spotkanie wynosi $10$. Istnieją trzy linie cięcia w odległościach $1,3,5$ od lewego skraju. Jeśli JOI-kun przetnie mizuyokan wzdłuż linii w odległościach $3,5$ od lewego skraju, otrzyma trzy kawałki. Ciąg długości kawałków to $(3,2,5)$ i jest zygzakowaty. Ponieważ nie można otrzymać więcej niż trzech kawałków, wypisz $3$.

Ten przykład wejścia spełnia ograniczenia podzadań $1,2,3,5,6$.