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