F - 水ようかん 2 (Mizuyokan 2) Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

Score: 100 points

Problem Statement

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, \ldots, 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 \le i \le 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 \le i \le N).

JOI-kun has a plan to organize Q tea parties. The j-th tea party (1 \le j \le 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, \ldots, x_m) is called zigzag if one (or both) of the following conditions are satisfied:

  • For k = 1, 2, \ldots, 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, \ldots, 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.


Input

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

Output

Write Q lines to the standard output. The j-th line (1 \le j \le 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 \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).
  • Given values are all integers.

Subtasks

  1. (6 points) N \le 200, Q \le 10.
  2. (9 points) N \le 2\,000, Q \le 10.
  3. (13 points) Q \le 10.
  4. (32 points) Y_j = L_{X_j} (1 \le j \le Q).
  5. (29 points) L_i \le 120\,000 (1 \le i \le N), Y_j \le 120\,000 (1 \le j \le Q).
  6. (11 points) No additional constraints.

Sample Input 1

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

Sample Output 1

3

In the first tea party, the parameters of the mizuyokan machine is 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.

Figure 1. The mizuyokan for the tea party

5 6 8 7 4

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.

5 6 8 7 4
5 6 8 7 4
5 6 8 7 4

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

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

Sample Output 2

1
2
3

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.

配点 : 100 点

問題文

水ようかんとは,おもに小豆からなる餡を型に流し込んで寒天で固めることにより作られる和菓子である.

いま,JOI 君の手元には水ようかん製造機がある.この水ようかん製造機は横長の直方体の形をした水ようかんを製造し,その水ようかんには縦方向の切れ目が N - 1 箇所に入る.水ようかんの長さと切れ目の位置は,水ようかん製造機に設定されている N 個のパラメータ d_1, d_2, \ldots, d_N によって定まる.水ようかんの長さは d_1 + d_2 + \cdots + d_N であり,左から i - 1 番目と i 番目 (1 \leqq i \leqq N) の切れ目の間の長さは d_i である.ただし,水ようかんの左端を 0 番目の切れ目,右端を N 番目の切れ目とみなす.はじめ,水ようかん製造機のパラメータは d_i = L_i (1 \leqq i \leqq N) に設定されている.

JOI 君は Q 回のお茶会を計画している.j 回目 (1 \leqq j \leqq Q) のお茶会の内容は整数 X_j, Y_j, A_j, B_j で表され,その手順は以下の通りである.

  1. 水ようかん製造機のパラメータ d_{X_j} の値を Y_j に更新する.
  2. 水ようかん製造機で,新しい水ようかんを 1 つ製造し,A_j 番目の切れ目から B_j 番目の切れ目の間の部分を切り出し,お茶会に使用する.残りの部分は JOI 君が食べる.
  3. お茶会に使用する部分の水ようかんを,いくつかの切れ目に沿って 1 個以上のピースに切り分ける.このとき,得られるピースの長さをそのピースのもともとの位置が左にあるものから順に並べた数列がジグザグになる,という条件を満たすようにする.

ただし,数列がジグザグであるとは,数列の要素が増加と減少を交互に繰り返していることをいう.例えば,数列 (2, 9, 2, 7),(7, 1, 9, 4, 6),(5),(2, 1) はジグザグであるが,数列 (1, 2, 3),(7, 1, 4, 4, 6),(2, 2) はジグザグではない.厳密には,数列 (x_1, x_2, \ldots, x_m) がジグザグであるとは,その数列が以下の 2 つの条件のいずれかを満たすことをいう.

  • k = 1, 2, \ldots, m - 1 に対して,k が奇数ならば x_k < x_{k+1} を,k が偶数ならば x_k > x_{k+1} を満たす.
  • k = 1, 2, \ldots, m - 1 に対して,k が奇数ならば x_k > x_{k+1} を,k が偶数ならば x_k < x_{k+1} を満たす.

JOI 君は,できるだけ多くの友達に水ようかんをふるまうため,それぞれのお茶会の手順 3. において得られるピースの個数をできるだけ多くしたい.

水ようかん製造機のパラメータの初期値とお茶会の計画の情報が与えられるので,それぞれのお茶会において,条件を満たすような切り分け方で得られるピースの個数の最大値を求めるプログラムを作成せよ.なお,この問題の制約下では,条件を満たすように水ようかんを切り分ける方法が必ず存在する.


入力

入力は以下の形式で標準入力から与えられる.

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

出力

標準出力に Q 行出力せよ.j 行目 (1 \leqq j \leqq Q) には,j 回目のお茶会において,条件を満たすような切り分け方で得られるピースの個数の最大値を出力せよ.


制約

  • 1 \leqq N \leqq 250\,000.
  • 1 \leqq L_i \leqq 10^9 (1 \leqq i \leqq N).
  • 1 \leqq Q \leqq 50\,000.
  • 1 \leqq X_j \leqq N (1 \leqq j \leqq Q).
  • 1 \leqq Y_j \leqq 10^9 (1 \leqq j \leqq Q).
  • 0 \leqq A_j < B_j \leqq N (1 \leqq j \leqq Q).
  • 入力される値はすべて整数である.

小課題

  1. (6 点) N \leqq 200,Q \leqq 10.
  2. (9 点) N \leqq 2\,000,Q \leqq 10.
  3. (13 点) Q \leqq 10.
  4. (32 点) Y_j = L_{X_j} (1 \leqq j \leqq Q).
  5. (29 点) L_i \leqq 120\,000 (1 \leqq i \leqq N),Y_j \leqq 120\,000 (1 \leqq j \leqq Q).
  6. (11 点) 追加の制約はない.

入力例 1

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

出力例 1

3

1 回目のお茶会において,水ようかん製造機のパラメータは (d_1, d_2, d_3, d_4, d_5, d_6) = (5, 6, 8, 7, 4, 9) となる.お茶会には,表 1 に示すような 0 番目の切れ目と 5 番目の切れ目の間の部分を使用する.

表 1 お茶会で使用する水ようかん.

5 6 8 7 4

例えば,表 2 のような切り分け方が考えられる.

表 2 水ようかんの切り分け方の例 3 つ.上から方法 1, 2, 3 とする.

5 6 8 7 4
5 6 8 7 4
5 6 8 7 4

方法 1 ではピースの長さが順に 5, 14, 7, 4 となっており,この数列はジグザグではないので条件を満たさない.一方,方法 2 ではピースの長さが順に 11, 8, 11 となっており,この数列はジグザグであるため条件を満たす.また,方法 3 ではピースの長さが順に 30 となっており,この数列もジグザグであるため条件を満たす.

方法 2 のようにして,条件を満たすような切り分け方で 3 個のピースを得ることができる.また,条件を満たすような切り分け方で 4 個以上のピースを得ることはできない.よって,1 行目には 3 を出力する.

この入力例はすべての小課題の制約を満たす.


入力例 2

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

出力例 2

1
2
3

1 回目のお茶会では,お茶会に使用する水ようかんの長さは 4 であり,左から長さ 2 の位置に切れ目がある.このとき,切り分けずにそのまま使用することで 1 個のピースが得られる.得られるピースの長さを順に並べた数列は (4) であり,これはジグザグである.これよりも多くのピースを得ることはできないので,1 を出力する.

2 回目のお茶会では,お茶会に使用する水ようかんの長さは 9 であり,左から長さ 2, 4 の位置に切れ目がある.このとき,左から長さ 4 の位置の切れ目で切ることで,2 個のピースが得られる.得られるピースの長さを順に並べた数列は (4, 5) であり,これはジグザグである.これよりも多くのピースを得ることはできないので,2 を出力する.

3 回目のお茶会では,お茶会に使用する水ようかんの長さは 10 であり,左から長さ 1, 3, 5 の位置に切れ目がある.このとき,左から長さ 3, 5 の位置の切れ目で切ることで,3 個のピースが得られる.得られるピースの長さを順に並べた数列は (3, 2, 5) であり,これはジグザグである.これよりも多くのピースを得ることはできないので,3 を出力する.

この入力例は小課題 1, 2, 3, 5, 6 の制約を満たす.


Source Name

JOI 2022/2023 春季トレーニング Contest Day2 問題3