水羊羹（Mizuyokan）是一种由红豆沙和琼脂制成的日式糕点，通常被凝固成矩形。

现在，JOI 君拥有一台水羊羹机。使用这台机器，JOI 君可以制作出一个长条矩形水羊羹，并带有 $N - 1$ 条垂直切割线。水羊羹的长度和切割线的位置由机器上设置的 $N$ 个参数 $d_1, d_2, \dots, d_N$ 决定。水羊羹的总长度为 $d_1 + d_2 + \dots + d_N$。从左侧数第 $i$ 条切割线（$1 \le i \le N$）与第 $(i-1)$ 条切割线之间的距离为 $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$ 描述，流程如下：

1. 更新水羊羹机器的参数 $d_{X_j}$，将其设置为 $Y_j$。
2. JOI 君使用水羊羹机制作一个新的水羊羹。他取下第 $A_j$ 条切割线和第 $B_j$ 条切割线之间的部分用于茶会，其余部分吃掉。
3. JOI 君沿着部分切割线将用于茶会的水羊羹切开。他将这部分水羊羹切成一块或多块。在此过程中，必须满足以下条件：如果将切好的碎片按原始位置从左到右排列，其长度序列必须是“之字形（zigzag）”的。

在此，如果一个序列的元素交替增大和减小，则称该序列为之字形。例如，序列 $(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, \dots, x_m)$ 满足以下两个条件之一（或两者），则称其为之字形： 对于 $k = 1, 2, \dots, m - 1$，当 $k$ 为奇数时满足 $x_k < x_{k+1}$，当 $k$ 为偶数时满足 $x_k > x_{k+1}$。 对于 $k = 1, 2, \dots, m - 1$，当 $k$ 为奇数时满足 $x_k > x_{k+1}$，当 $k$ 为偶数时满足 $x_k < x_{k+1}$。

由于 JOI 君希望尽可能多地招待朋友，他想要最大化步骤 3 中获得的碎片数量。

请编写一个程序，在给定水羊羹机器的初始参数和茶会计划的情况下，计算每场茶会中通过切割水羊羹所能获得的最大碎片数量。注意，在题目给定的约束条件下，总是可以切开水羊羹以满足条件。

输入格式

从标准输入读取以下数据：

$N$

$L_1 \ L_2 \ \dots \ 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 \le j \le Q$）对应第 $j$ 场茶会，包含满足条件的情况下切割水羊羹所能获得的最大碎片数量。

数据范围

• $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$）
• 给定值均为整数。

子任务

1. (6 分) $N \le 200, Q \le 10$
2. (9 分) $N \le 2\,000, Q \le 10$
3. (13 分) $Q \le 10$
4. (32 分) $Y_j = L_{X_j}$（$1 \le j \le Q$）
5. (29 分) $L_i \le 120\,000$（$1 \le i \le N$）, $Y_j \le 120\,000$（$1 \le j \le Q$）
6. (11 分) 无附加约束。

样例

样例输入 1

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

样例输出 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