P10284 [USACO24OPEN] Splitting Haybales P

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$ 行，包含每个询问的答案。

### 样例解释 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$：没有额外限制。