Mizuyokan é um doce japonês feito de pasta de feijão azuki. É preparado cozinhando a pasta de feijão azuki com ágar e solidificando a mistura numa forma retangular.

Agora, JOI-kun tem uma máquina de mizuyokan. Com ela, JOI-kun pode fazer um mizuyokan retangular comprido na horizontal, com $N-1$ linhas de corte verticais. O comprimento do mizuyokan e as posições das linhas de corte são determinados pelos $N$ parâmetros $d_1,d_2,\ldots,d_N$ definidos na máquina. O comprimento do mizuyokan é $d_1+d_2+\cdots+d_N$. A distância entre a $(i-1)$-ésima linha de corte e a $i$-ésima linha de corte, contadas da esquerda, é $d_i$ ($1\le i\le N$). Aqui, consideramos a extremidade esquerda do mizuyokan como a linha de corte de índice $0$ e a extremidade direita como a linha de corte de índice $N$. Inicialmente, os parâmetros da máquina de mizuyokan satisfazem $d_i=L_i$ ($1\le i\le N$).

JOI-kun planeia organizar $Q$ festas de chá. A $j$-ésima festa de chá ($1\le j\le Q$) é descrita pelos inteiros $X_j,Y_j,A_j,B_j$. A festa decorre da seguinte forma.

1. O parâmetro $d_{X_j}$ da máquina de mizuyokan é atualizado para $Y_j$.
2. JOI-kun faz um novo mizuyokan com a máquina. Retira a parte do mizuyokan entre as linhas de corte de índices $A_j$ e $B_j$ e usa-a na festa de chá. Come o resto.
3. JOI-kun corta a parte do mizuyokan destinada à festa de chá ao longo de algumas linhas de corte, dividindo-a em um ou mais pedaços. Neste processo, deve ser satisfeita a seguinte condição: se os pedaços forem ordenados da esquerda para a direita, nas suas posições originais, a sequência dos comprimentos dos pedaços deve ser em ziguezague.

Aqui, uma sequência é chamada de ziguezague se os seus elementos aumentam e diminuem alternadamente. Por exemplo, as sequências $(2,9,2,7)$, $(7,1,9,4,6)$, $(5)$ e $(2,1)$ são em ziguezague, mas as sequências $(1,2,3)$, $(7,1,4,4,6)$ e $(2,2)$ não são. Mais precisamente, uma sequência $(x_1,x_2,\ldots,x_m)$ é chamada de ziguezague se uma das seguintes condições (ou ambas) for satisfeita:

• Para $k=1,2,\ldots,m-1$, a desigualdade $x_k<x_{k+1}$ é satisfeita se $k$ for ímpar, e a desigualdade $x_k>x_{k+1}$ é satisfeita se $k$ for par.
• Para $k=1,2,\ldots,m-1$, a desigualdade $x_k>x_{k+1}$ é satisfeita se $k$ for ímpar, e a desigualdade $x_k<x_{k+1}$ é satisfeita se $k$ for par.

Como JOI-kun quer dar mizuyokan ao maior número possível de amigos, pretende maximizar o número de pedaços obtidos no passo 3 da festa de chá.

Escreva um programa que, dados os parâmetros iniciais da máquina de mizuyokan e o plano das festas de chá, calcule, para cada festa de chá, o maior número possível de pedaços obtidos ao cortar a parte do mizuyokan de modo a satisfazer a condição. Note que, sob as restrições deste problema, é sempre possível cortar a parte do mizuyokan de modo a satisfazer a condição.

Entrada

Leia os seguintes dados da entrada padrão.

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

Saída

Escreva $Q$ linhas na saída padrão. A $j$-ésima linha ($1\le j\le Q$) corresponde à $j$-ésima festa de chá e contém o maior número possível de pedaços obtidos ao cortar a parte do mizuyokan nessa festa de modo a satisfazer a condição.

Restrições

• $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$).
• Todos os valores fornecidos são inteiros.

Subtarefas

1. (6 pontos) $N\le 200$, $Q\le 10$.
2. (9 pontos) $N\le 2\,000$, $Q\le 10$.
3. (13 pontos) $Q\le 10$.
4. (32 pontos) $Y_j=L_{X_j}$ ($1\le j\le Q$).
5. (29 pontos) $L_i\le 120\,000$ ($1\le i\le N$), $Y_j\le 120\,000$ ($1\le j\le Q$).
6. (11 pontos) Sem restrições adicionais.

Exemplos

Entrada 1

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

Saída 1

3

Explicação

Na primeira festa de chá, os parâmetros da máquina de mizuyokan são definidos como $(d_1,d_2,d_3,d_4,d_5,d_6)=(5,6,8,7,4,9)$. JOI-kun usa a parte do mizuyokan entre as linhas de corte de índices $0$ e $5$, como na Figura 1.

Figura 1. O mizuyokan para a festa de chá

Por exemplo, JOI-kun pode cortar a parte do mizuyokan da seguinte forma.

Figura 2. Três métodos para cortar o mizuyokan. De cima para baixo: Método 1, Método 2, Método 3.

No Método 1, os comprimentos dos pedaços são $5,14,7,4$. Como esta sequência não é em ziguezague, não satisfaz a condição. Por outro lado, no Método 2, os comprimentos dos pedaços são $11,8,11$. Como esta sequência é em ziguezague, satisfaz a condição. No Método 3, o comprimento do pedaço é $30$. Como esta sequência é em ziguezague, também satisfaz a condição.

Se JOI-kun cortar a parte do mizuyokan pelo Método 2, obtém 3 pedaços. Como não é possível cortá-la de modo a satisfazer a condição e obter 4 ou mais pedaços, escreva 3 na primeira linha.

Esta entrada de exemplo satisfaz as restrições de todas as subtarefas.

Entrada 2

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

Saída 2

1
2
3

Explicação

Na primeira festa de chá, o comprimento da parte do mizuyokan destinada à festa é $4$. Há uma linha de corte a uma distância de $2$ da extremidade esquerda. Se JOI-kun usar o mizuyokan sem o cortar, obtém um pedaço. A sequência dos comprimentos dos pedaços é $(4)$, que é em ziguezague. Como não pode obter mais de um pedaço, escreva 1.

Na segunda festa de chá, o comprimento da parte do mizuyokan destinada à festa é $9$. Há duas linhas de corte a distâncias de $2,4$ da extremidade esquerda. Se JOI-kun cortar o mizuyokan na linha de corte a uma distância de $4$ da extremidade esquerda, obtém dois pedaços. A sequência dos comprimentos dos pedaços é $(4,5)$, que é em ziguezague. Como não pode obter mais de dois pedaços, escreva 2.

Na terceira festa de chá, o comprimento da parte do mizuyokan destinada à festa é $10$. Há três linhas de corte a distâncias de $1,3,5$ da extremidade esquerda. Se JOI-kun cortar o mizuyokan nas linhas de corte a distâncias de $3,5$ da extremidade esquerda, obtém três pedaços. A sequência dos comprimentos dos pedaços é $(3,2,5)$, que é em ziguezague. Como não pode obter mais de três pedaços, escreva 3.

Esta entrada de exemplo satisfaz as restrições das Subtarefas 1, 2, 3, 5, 6.