E. 乌龟与兔子赛跑：最优训练

每次测试的时间限制：5 秒
每次测试的内存限制：256 兆字节

Isaac 开始他的训练。一共有 $n$ 条跑道，第 $i$ 条跑道（$1 \le i \le n$）由 $a_i$ 个长度相等的路段组成。

给定一个整数 $u$（$1 \le u \le 10^9$），完成每个路段会使 Isaac 的能力按如下规则变化：

• 完成第 $1$ 段，能力增加 $u$
• 完成第 $2$ 段，能力增加 $u-1$
• 完成第 $3$ 段，能力增加 $u-2$
• ……
• 完成第 $k$ 段（$k \ge 1$），能力增加 $u+1-k$
  （$u+1-k$ 可能为负数，表示多完成一段反而会降低 Isaac 的能力）

你还会得到一个整数 $l$。你必须选择一个整数 $r$，满足 $l \le r \le n$，Isaac 将完成第 $l, l+1, \dots, r$ 条跑道上的每一个路段（即总共完成 $\sum_{i=l}^r a_i = a_l + a_{l+1} + \dots + a_r$ 个路段）。

问题是：选择哪个 $r$ 能使 Isaac 能力的总增加量最大？

如果存在多个 $r$ 都能使能力增加量达到最大，输出最小的那个 $r$。

为了增加难度，你需要对 $q$ 个不同的 $(l, u)$ 查询回答上述问题。

---

输入

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的描述如下：

• 第一行包含一个整数 $n$（$1 \le n \le 10^5$）
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, 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$）—— 每个查询的描述。

所有测试用例的 $n$ 总和不超过 $2 \cdot 10^5$。所有测试用例的 $q$ 总和不超过 $2 \cdot 10^5$。

---

输出

对于每个测试用例，输出 $q$ 个整数：第 $i$ 个整数是第 $i$ 个查询的最优 $r$。如果有多个解，输出最小的 $r$。

---

示例

输入

5
6
3 1 4 1 5 9
3
1 8
2 7
5 9
1
10
1
1 1
9
5 10 9 6 8 3 10 7 3
5
8 56
1 12
9 3
1 27
5 45
5
7 9 2 5 2
10
1 37
2 9
3 33
4 32
4 15
2 2
4 2
2 19
3 7
2 7
10
9 1 6 7 6 3 10 7 3 10
5
10 43
3 23
9 3
6 8
5 14

输出

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

---

注释

对于第一个测试用例的第一个查询：

• 选择 $r=3$，Isaac 完成 $a_1+a_2+a_3 = 3+1+4 = 8$ 段，能力增加为：
  $u + (u-1) + \dots + (u-7) = 8+7+6+5+4+3+2+1 = 36$
• 选择 $r=4$，Isaac 完成 $a_1+a_2+a_3+a_4 = 3+1+4+1 = 9$ 段，能力增加为：
  $u + (u-1) + \dots + (u-8) = 8+7+6+5+4+3+2+1+0 = 36$

两种选择能力增加相同，但我们要选最小的 $r$，所以选 $r=3$。

对于第二个查询，选 $r=4$，完成 $a_2+a_3+a_4 = 1+4+1=6$ 段，能力增加为：
$7+6+5+4+3+2 = 27$，是最优的。

对于第三个查询：

• 选 $r=5$，完成 $a_5=5$ 段，能力增加：$9+8+7+6+5 = 35$
• 选 $r=6$，完成 $a_5+a_6 = 5+9 = 14$ 段，能力增加：
  $9+8+7+6+5+4+3+2+1+0+(-1)+(-2)+(-3)+(-4) = 35$

能力相同，选最小的 $r$，即 $r=5$。

因此第一个测试用例的输出是 [3,4,5]。