27997번 - Mizuyokan 2 서브태스크다국어

Mizuyokan is a Japanese confectionery made of azuki beans paste. It was made by cooking azuki beans paste with agar, and solidifying them in a rectangular-shaped form.

Now, JOI-kun has a mizuyokan machine. Using it, JOI-kun can make a horizontally long rectangular-shaped mizuyokan with $N - 1$ vertical cutlines. The length of the mizuyokan and the positions of the cutlines are determined by the $N$ parameters $d_1, d_2, \dots , d_N$ set on the machine. The length of the mizuyokan is $d_1 + d_2 + \cdots + d_N$. The distance between the $(i - 1)$-th cutline ($1 ≤ i ≤ N$) from the left and the $i$-th cutline from the left is $d_i$. Here, we consider the leftmost edge of the mizuyokan as the $0$-th cutline, and the rightmost edge of the mizuyokan as the $N$-th cutline. In the beginning, the parameters of the mizuyokan machine satisfy $d_i = L_i$ ($1 ≤ i ≤ N$).

JOI-kun has a plan to organize $Q$ tea parties. The $j$-th tea party ($1 ≤ j ≤ Q$) is described by the integers $X_j$, $Y_j$, $A_j$, $B_j$. It proceeds as follows.

1. The parameter $d_{X_j}$ of the mizuyokan machine is updated, and it is set as $Y_j$.
2. JOI-kun makes a new mizuyokan using the mizuyokan machine. He takes the part of the mizuyokan between the $A_j$-th cutline and the $B_j$-th cutline, and uses it for the tea party. He eats the rest.
3. JOI-kun cuts the part of the mizuyokan for the tea party along some of the cutlines. He cuts the part of the mizuyokan into one or more pieces. In this process, the following condition should be satisfied: if the pieces are ordered from the left as in the original positions, the sequence of the lengths of the pieces is zigzag.

Here, a sequence is called zigzag if the elements of the sequence increase and decrease alternately. For example, the sequences $(2, 9, 2, 7)$, $(7, 1, 9, 4, 6)$, $(5)$, $(2, 1)$ are zigzag, but the sequences $(1, 2, 3)$, $(7, 1, 4, 4, 6)$, $(2, 2)$ are not zigzag. Precisely, a sequence $(x_1, x_2, \dots , x_m)$ is called zigzag if one (or the both) of the following conditions are satisfied:

• For $k = 1, 2, \dots , m - 1$, the inequality $x_k < x_{k+1}$ is satisfied if $k$ is odd, and the inequality $x_k > x_{k+1}$ is satisfied if $k$ is even.
• For $k = 1, 2, \dots , m - 1$, the inequality $x_k > x_{k+1}$ is satisfied if $k$ is odd, and the inequality $x_k < x_{k+1}$ is satisfied if $k$ is even.

Since JOI-kun wants to give mizuyokan to as many friends as possible, he wants to maximize the number of pieces obtained by the procedure 3. of the tea party.

Write a program which, given information of the initial parameters of the mizuyokan machine and the plan of the tea parties, calculates, for each tea party, the maximum possible number of pieces obtained by cutting the part of the mizuyokan so that the condition is satisfied. Note that, under the constraints of this task, it is always possible to cut the part of the mizuyokan so that the condition is satisfied.

Read the following data from the standard input.

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

Write $Q$ lines to the standard output. The $j$-th line ($1 ≤ j ≤ Q$) of output corresponds to the $j$-th tea party. It contains the maximum possible number of pieces obtained by cutting the part of the mizuyokan in the $j$-th tea party so that the condition is satisfied.

• $1 ≤ N ≤ 250\,000$.
• $1 ≤ L_i ≤ 10^9$ ($1 ≤ i ≤ N$).
• $1 ≤ Q ≤ 50\,000$.
• $1 ≤ X_j ≤ N$ ($1 ≤ j ≤ Q$).
• $1 ≤ Y_j ≤ 10^9$ ($1 ≤ j ≤ Q$).
• $0 ≤ A_j < B_j ≤ N$ ($1 ≤ j ≤ Q$).
• Given values are all integers.