题目描述

Farmer John 想要将干草堆公平地分配给他最喜欢的两头奶牛 Bessie 和 Elsie。他有 $N$（$1\le N\le 2\cdot 10^5$）个降序排序的干草堆，其中第 $i$ 个干草堆有 $a_i$ 单位干草（$2\cdot 10^5\ge a_1\ge a_2\ge \cdots \ge a_N\ge 1$）。

Farmer John 正在考虑将一个连续区间的干草堆 $a_l,\ldots,a_r$ 分配给 Bessie 和 Elsie。他决定按从 $l$ 到 $r$ 的顺序处理干草堆，当处理第 $i$ 个干草堆时他会将其交给当前干草较少的奶牛（如果并列，他会将其交给 Bessie）。

给定 $Q$（$1\le Q\le 2\cdot 10^5$）个询问，每个询问包含三个整数 $l,r,x$（$1\le l\le r\le N$，$|x|\le 10^9$）。对于每个询问，输出如果 Bessie 初始时比 Elsie 多 $x$ 单位干草，在处理干草堆 $l$ 到 $r$ 后 Bessie 将比 Elsie 多多少单位的干草。注意如果 Elsie 最终获得的干草多于 Bessie 则该值为负。

输入格式

输入的第一行包含 $N$。

第二行包含 $a_1\ldots a_N$。

第三行包含 $Q$。

以下 $Q$ 行包含 $l,r,x$。

输出格式

输出 $Q$ 行，包含每个询问的答案。

2
3 1
15
1 1 -2
1 1 -1
1 1 0
1 1 1
1 1 2
1 2 -2
1 2 -1
1 2 0
1 2 1
1 2 2
2 2 -2
2 2 -1
2 2 0
2 2 1
2 2 2

1
2
3
-2
-1
0
1
2
-1
0
-1
0
1
0
1

5
4 4 3 1 1
7
1 1 20
1 2 20
1 5 20
1 1 0
1 5 0
1 4 0
3 5 2

16
12
7
4
1
2
1

提示

样例解释 1

对于第 1 个询问，Elsie 初始时比 Bessie 多 2 单位干草。然后，在处理干草堆 1 后，Bessie 将收到 3 单位干草，从而 Bessie 将比 Elsie 多 1 单位干草。

对于第 3 个询问，Elsie 和 Bessie 初始时有相同的干草数量。在处理干草堆 1 后，Bessie 将收到 3 单位干草，从而 Bessie 将比 Elsie 多 3 单位干草。

对于第 9 个询问，Bessie 初始时比 Elsie 多 1 单位干草，然后在处理第 1 个干草堆后，比 Elsie 少 2 单位干草，处理第 2 个干草堆后，比 Elsie 少 1 单位干草。

样例解释 2

对于第 5 个询问，有 5 个干草堆需要处理。Bessie 收到 4 单位干草，然后 Elsie 收到 4 单位干草，然后 Bessie 收到 3 单位干草，然后 Elsie 收到 1 单位干草，然后 Elsie 收到 1 单位干草。

测试点性质

• 测试点 $3$：$Q\le 100$。
• 测试点 $4-6$：至多存在 $100$ 个不同的 $a_i$。
• 测试点 $7-22$：没有额外限制。