SIMO的资源拾取

SIMO的基地总共由有 $n$ 个不同的场地，每个场地有 $a_i$​ 个补给品，其中 $i$ 表示第 $i$ 个场地。SIMO决定在接下来的一段时间内，从第 $l$ 个场地次开始，连续拾取一定数量场地中的所有的补给品，直到第 $r$ 个场地。

每个补给品的补充的能量如下：

• 第 $1$ 个补给品可以补充的能量是 $u$ 单位。
• 第 $2$ 个补给品可以补充的能量是 $u−1$ 单位。
• 第 $3$ 个补给品可以补充的能量是 $u−2$ 单位。
• 以此类推，直到第 $k$ 个补给品可以补充的能量是 $u+1−k$ 单位。

凡事必有两面性，当然，如果 $k>u$，则你将会消耗能量，意味着拾取这个补给品将会消耗你的能量。

SIMO的目标是选择一个结束场地 $r$（满足 $l≤r≤n$），以最大化从第 $l$ 批次到第 $r$ 批次的能量。

输入

第一行包含一个整数 $n$ （ $1 \le n \le 10^5$ ）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ （ $1 \le a_i \le 10^4$ ）。

第三行包含一个整数 $q$ （ $1 \le q \le 10^5$ ）。

接下来的 $q$ 行分别包含两个整数 $l$ 和 $u$ （ $1 \le l \le n, 1 \le u \le 10^9$ ）—每个查询的描述。

回答以下问题：什么是最优的 $r$ ，可以获得最大的能量？

如果有多个 $r$ 使利益最大化，则输出最小的 $r$ 。

输出

输出 $q$ 整数：第 $i$ 个整数包含第 $i$ 个查询的最优 $r$ 。如果有多个解决方案，则输出最小的一个。

样例

输入样例1

6
3 1 4 1 5 9
3
1 8
2 7
5 9

输出样例1

3
4
5

注意

对于第 $1$ 个查询：

通过选择 $r = 3$ ，总共拾取了 $a_1 + a_2 + a_3 = 3 + 1 + 4 = 8$ 个补给品， 因此，他的总能量为 $u+(u-1)+\ldots+(u-7)=8+7+6+5+4+3+2+1 = 36$ 。 通过选择 $r = 4$ ，总共拾取了 $a_1 + a_2 + a_3 + a_4 = 3 + 1 + 4 + 1 = 9$ 个产品， 因此，他的总能量为 $u+(u-1)+\ldots+(u-8)=8+7+6+5+4+3+2+1+0 = 36$ 。 这两种选择都会获得最佳的能量，但我们希望选择最小的 $r$ 。所以我们选择 $r = 3$ 。