当前没有测试数据。

一、题目名称

分割干草捆（Splitting Haybales）

二、题目描述

农夫约翰（Farmer John）想在他最喜欢的两头奶牛贝西（Bessie）和埃尔西（Elsie）之间公平地分割干草捆。他有$N$（$1\leq N\leq2\cdot10^5$）个干草捆，按非递增顺序排列，其中第$i$个干草捆有$a_i$单位的干草（$2\cdot10^5\geq a_1\geq a_2\geq\cdots\geq a_N\geq1$）。

农夫约翰正在考虑在贝西和埃尔西之间分割一段连续的干草捆$a_l,\cdots,a_r$。他决定按顺序从$l$到$r$处理干草捆，当处理第$i$个干草捆时，他会把它给当前干草较少的奶牛（如果数量相同，他会给贝西）。

给定$Q$（$1\leq Q\leq2\cdot10^5$）个查询，每个查询有三个整数$l,r,x$（$1\leq l\leq r\leq N$，$\vert x\vert\leq10^9$）。对于每个查询，输出在处理干草捆$l$到$r$后，贝西比埃尔西多的干草单位数，如果贝西一开始比埃尔西多$x$单位干草。注意，如果埃尔西最终的干草捆比贝西多，这个值为负。

三、输入格式（从终端/标准输入读取）

1. 第一行包含$N$。
2. 第二行包含$a_1\cdots a_N$。
3. 第三行包含$Q$。
4. 接下来$Q$行包含$l,r,x$。

四、输出格式（打印输出到终端/标准输出）

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

五、样例输入及输出

样例输入1

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

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

解释：对于第一个查询，埃尔西一开始比贝西多$2$单位干草。然后，在处理第一个干草捆后，贝西将收到$3$单位干草，贝西将比埃尔西多$1$单位干草。对于第三个查询，埃尔西和贝西一开始干草数量相同。在处理第一个干草捆后，贝西将收到$3$单位干草，贝西将比埃尔西多$3$单位干草。对于第九个查询，贝西一开始比埃尔西多$1$单位干草，然后在处理第一个干草捆后，比埃尔西少$2$单位干草，在处理第二个干草捆后，比埃尔西少$1$单位干草。

样例输入2

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

样例输出2

16
12
7
4
1
2
1

解释：在第五个查询中，有$5$个干草捆要处理。贝西收到$4$单位干草，然后埃尔西收到$4$单位干草，然后贝西收到$3$单位干草，然后埃尔西收到$1$单位干草，然后埃尔西收到$1$单位干草。

六、评分规则

1. 输入3：$Q\leq100$。
2. 输入4 - 6：最多有$100$个不同的$a_i$。
3. 输入7 - 22：无其他额外约束。

题目来源：Benjamin Qi。