题目描述

水羊羹是一种用红豆沙制成的日式点心，将红豆沙与琼脂混合，并用矩形模具定型，这样就可以做成水羊羹了。

现在 JOI 君有一台 水羊羹机器。使用它，JOI 君可以制作一个横向的矩形水羊羹，其上有 $N-1$ 条垂直切割线。水羊羹的长度和切割线位置由机器上设置的 $N$ 个参数 $d_1,d_2,\ldots,d_N$ 确定。水羊羹的长度为 $d_1+d_2+\ldots+d_N$。从左到右第 $(i-1)\ (1\le i\le N)$ 条切割线与第 $i$ 条切割线之间的距离为 $d_i$。这里，我们考虑水羊羹的最左边为第 $0$ 条切割线，水羊羹的最右边为第 $N$ 条切割线。最初，水羊羹机器的参数满足 $d_i=L_i\ (1\le i\le N)$。

JOI 君计划组织 $Q$ 次茶会。第 $j\ (1\le j\le Q)$ 次茶会由整数 $X_j,Y_j,A_j,B_j$ 表示。茶会按如下方式进行：

• 水羊羹机器的参数 $d_{X_j}$ 被更新，并设置为 $Y_j$。
• JOI 君用水羊羹机器只做了一个新的水羊羹。他把水羊羹在第 $A_j$ 条切割线和第 $B_j$ 条切割线之间的部分取出，用于茶会。他吃掉了剩余部分。
• JOI 君沿一些切割线来切为茶会准备的水羊羹。他会将水羊羹切为一或更多块。在这个过程中应满足以下条件：如果这些切好的水羊羹块按最初的位置从左到右排列，那么这些水羊羹块的长度序列应该是 锯齿形 的。

这里，如果序列中元素交替上升和下降，就称这个序列是锯齿形的。例如，序列 $(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)$ 被称为锯齿形的，当且仅当以下条件中至少一个被满足：

• 对于 $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≤j≤Q)$ 应当包含第 $j$ 场茶会中的所选小片的最大数量。

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

3

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

1
2
3

提示

对于所有输入数据，满足：

• $1\le N \le 2.5\times 10^5$
• $1\le L_i \le 10^9$
• $1\le Q\le5\times10^4$
• $1\le X_j\le N,1\le Y_j\le 10^9$
• $0\le A_j < B_j \le N$

详细子任务附加限制及分值如下表所示。