最近,加密货币变得越来越流行。安决定是时候开始挖掘狗狗币加密货币了。 Ann 的计算机功能不是很强大,因此 Ann 每天正好开采 $$$1$$$ 狗狗币。在互联网上,有对未来 $$$n$$$ 天的 $$$1$$$ 狗狗币成本的预测。每天,安都可以出售她目前拥有的任意数量的狗狗币。请注意,如果 Ann 在第 $$$i$$$ 天开采狗狗币,那么她可以在同一天出售它。
安尚未决定何时开始挖矿。她准备了 $$$q$$$ 可能的计划,并且对于每个计划她都想知道她可以获得的最大利润。每个计划都由两个数字 $$$l$$$ 和 $$$r$$$ 描述 - 采矿的第一天和最后一天。请注意,在第 $$$r$$$ 天之后,Ann 不应留下任何狗狗币。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 10^6$$$),其中 $$$c_i$$$ 是狗狗币在第 $$$i$$$ 天的成本。
第三行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — Ann 的计划数量。
以下 $$$q$$$ 行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$) — 挖矿的第一天和最后一天。
输出
对于每个 Ann 的计划,打印一个整数 — 她使用该计划可以获得的最大利润。
示例
输入 #1
5 4 1 2 3 2 4 1 5 2 4 3 5 5 5
输出 #1
15 9 8 2