2023-sp_Mizuyokan_2 — JOI JOI_spring
Task type: batch | Time limit: 3 s | Memory limit: 1024 MB | Difficulty: 24
Algorithms: data structures, segment tree, coordinate compression, dynamic programming

# 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, . . . , *dN* set on the machine. The length of the mizuyokan is *d*1 + *d*2 + · · · + *dN*. The distance between the (*i* − 1)-th cutline (1 ≤ *i* ≤ *N*) from the left and the *i*-th cutline from the left is *di*. 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 *di* = *Li* (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 *Xj*, *Yj*, *Aj*, *Bj*. It proceeds as follows:

- The parameter *dXj* of the mizuyokan machine is updated, and it is set as *Yj*.
- JOI-kun makes a new mizuyokan using the mizuyokan machine. He takes the part of the mizuyokan between the *Aj*-th cutline and the *Bj*-th cutline, and uses it for the tea party. He eats the rest.
- 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, . . . , *xm*) is called zigzag if one (or both) of the following conditions are satisfied:

- For *k* = 1, 2, . . . , *m* − 1, the inequality *xk* < *xk*+1 is satisfied if *k* is odd, and the inequality *xk* > *xk*+1 is satisfied if *k* is even.
- For *k* = 1, 2, . . . , *m* − 1, the inequality *xk* > *xk*+1 is satisfied if *k* is odd, and the inequality *xk* < *xk*+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.

## Input

Read the following data from the standard input.

```
N
L1 L2 · · · LN
Q
X1 Y1 A1 B1
X2 Y2 A2 B2
.
.
.
XQ YQ AQ BQ
```

## Output

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.

## Constraints

- 1 ≤ *N* ≤ 250 000.
- 1 ≤ *Li* ≤ 109 (1 ≤ *i* ≤ *N*).
- 1 ≤ *Q* ≤ 50 000.
- 1 ≤ *Xj* ≤ *N* (1 ≤ *j* ≤ *Q*).
- 1 ≤ *Yj* ≤ 109 (1 ≤ *j* ≤ *Q*).
- 0 ≤ *Aj* < *Bj* ≤ *N* (1 ≤ *j* ≤ *Q*).
- Given values are all integers.

## Subtasks

1. (6 points) *N* ≤ 200, *Q* ≤ 10.
2. (9 points) *N* ≤ 2 000, *Q* ≤ 10.
3. (13 points) *Q* ≤ 10.
4. (32 points) *Yj* = *LXj* (1 ≤ *j* ≤ *Q*).
5. (29 points) *Li* ≤ 120 000 (1 ≤ *i* ≤ *N*), *Yj* ≤ 120 000 (1 ≤ *j* ≤ *Q*).
6. (11 points) No additional constraints.

## Sample Input and Output

| Sample Input 1   | Sample Output 1 |
| :--------------- | :-------------- |
| 6                | 3               |
| 5 6 8 7 4 9      |                 |
| 1                |                 |
| 6 9 0 5          |                 |

In the first tea party, the parameters of the mizuyokan machine are set as (*d*1, *d*2, *d*3, *d*4, *d*5, *d*6) = (5, 6, 8, 7, 4, 9). JOI-kun uses the part of the mizuyokan between the 0-th cutline and the 5-th cutline as in Figure 1.

For example, JOI-kun can cut the part of the mizuyokan as follows.

Figure 2. Three methods to cut the mizuyokan. Method 1, Method 2, Method 3 from the top.

In Method 1, the lengths of the pieces are 5, 14, 7, 4. Since this sequence is not zigzag, it does not satisfy the condition. On the other hand, in Method 2, the lengths of the pieces are 11, 8, 11. Since this sequence is zigzag, it satisfies the condition. In Method 3, the length of the piece is 30. Since this sequence is zigzag, it also satisfies the condition.

If JOI-kun cuts the part of the mizuyokan by Method 2, he gets 3 pieces. Since it is not possible for him to cut the part of the mizuyokan so that the condition is satisfied and he gets more than or equal to 4 pieces, output 3 in the first line.

This sample input satisfies the constraints of all the subtasks.

| Sample Input 2 | Sample Output 2 |
| :------------- | :-------------- |
| 4              | 1               |
| 6 2 3 6        | 2               |
| 3              | 3               |
| 3 2 1 3        |                 |
| 4 5 1 4        |                 |
| 1 1 0 4        |                 |

In the first tea party, the length of the part of the mizuyokan for the tea party is 4. There is a cutline whose distance is 2 from the leftmost edge. If JOI-kun uses the mizuyokan without cutting it, he gets one piece. The sequence of the lengths of the pieces is (4), which is zigzag. Since he cannot obtain more than one piece, output 1.

In the second tea party, the length of the part of the mizuyokan for the tea party is 9. There are two cutlines whose distances are 2, 4 from the leftmost edge. If JOI-kun cuts the mizuyokan at the cutline whose distance is 4 from the leftmost edge, he gets two pieces. The sequence of the lengths of the pieces is (4, 5), which is zigzag. Since he cannot obtain more than two pieces, output 2.

In the third tea party, the length of the part of the mizuyokan for the tea party is 10. There are three cutlines whose distances are 1, 3, 5 from the leftmost edge. If JOI-kun cuts the mizuyokan at the cutlines whose distances are 3, 5 from the leftmost edge, he gets three pieces. The sequence of the lengths of the pieces is (3, 2, 5), which is zigzag. Since he cannot obtain more than three pieces, output 3.

This sample input satisfies the constraints of Subtasks 1, 2, 3, 5, 6.

Starter code: