A6143 | 「USACO 2024 US Open Platinum」Splitting Haybales

**题目译自 [USACO 2024 US Open Contest, Platinum](http://usaco.org/index.php?page=open24results) Problem 2. [Splitting Haybales](http://usaco.org/index.php?page=viewproblem2&cpid=1429)**

FJ 想把干草公平地分给他最喜欢的两头奶牛 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 \ldots \ge a_N\ge 1)$ 单位的干草。

FJ 正在考虑把连续区间 $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$。

第二行 $N$ 个整数 $a_1,\ldots,a_N$。

第三行一个整数 $Q$。

接下来 $Q$ 行每行三个整数 $l,r,x$。

输出 $Q$ 行，代表每次查询的答案。