Problem 2. Splitting Haybales

USACO 2024 US Open Contest, Platinum

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 \dots \ge a_N \ge 1$）。

Farmer John 正在考虑将一个连续区间的干草堆 $a_l, \dots, 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\dots 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

对于第 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$ 单位干草。

输入样例：

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

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

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

供题：Benjamin Qi