艾萨克开始训练。有 $$$n$$$ 可用跑道,第 $$$i$$$ 跑道 ($$$1 \le i \le n$$$) 由 $$$a_i$$$ 等长部分组成。
给定一个整数$$$u$$$ ($$$1 \le u \le 10^9$$$),完成每个部分可以使Isaac的能力增加一定的值,描述如下:
- 完成 $$$1$$$-st 部分后,Isaac 的表现提高了 $$$u$$$。
- 完成 $$$2$$$-nd 部分后,Isaac 的表现提高了 $$$u-1$$$。
- 完成 $$$3$$$-rd 部分后,艾萨克的表现提高了 $$$u-2$$$。
- $$$\ldots$$$
- 完成第 $$$k$$$ 部分 ($$$k \ge 1$$$) 会使 Isaac 的表现提高 $$$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} + \ldots + a_r$$$ 部分)。
回答以下问题:您可以选择的最佳 $$$r$$$ 是什么,以最大可能提高 Isaac 的性能?
如果存在多个 $$$r$$$ 可以最大化 Isaac 性能的提升,则输出最小的 $$$r$$$。
为了增加难度,您需要回答 $$$q$$$ $$$l$$$ 和 $$$u$$$ 不同值的问题。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
测试用例的描述如下。
第一行包含一个整数 $$$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$$$) - 每个查询的描述。
所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。所有测试用例的 $$$q$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出 $$$q$$$ 整数:第 $$$i$$$ 个整数包含第 $$$i$$$ 查询的最佳 $$$r$$$ 。如果有多个解,则输出最小的一个。
示例
输入 #1
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
输出 #1
3 4 5 1 9 2 9 4 9 5 2 5 5 5 2 4 5 4 2 10 6 9 7 7
注意
对于第一个测试用例中的 $$$1$$$-st 查询:
- 通过选择 $$$r = 3$$$,Isaac 总共完成 $$$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$$$,Isaac 总共完成了 $$$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$$$。
对于第一个测试用例中的 $$$2$$$-nd 查询,通过选择 $$$r = 4$$$,Isaac 总共完成了 $$$a_2 + a_3 + a_4 = 1 + 4 + 1 = 6$$$ 部分,因此他的性能提升为$$$u+(u-1)+\ldots+(u-5)=7+6+5+4+3+2 = 27$$$。这是性能的最佳提升。
对于第一个测试用例中的 $$$3$$$-rd 查询:
- 通过选择 $$$r = 5$$$,Isaac 总共完成 $$$a_5 = 5$$$ 部分,因此他的性能提升为 $$$u+(u-1)+\ldots+(u-4)=9+8+7+6+5 = 35$$$。
- 通过选择 $$$r = 6$$$,Isaac 总共完成了 $$$a_5 + a_6 = 5 + 9 = 14$$$ 部分,因此他的性能提升为$$$u+(u-1)+\ldots+(u-13)=9+8+7+6+5+4+3+2+1+0+(-1)+(-2)+(-3)+(-4) = 35$$$。
两种选择都能获得最佳的性能提升,但我们希望选择最小的$$$r$$$。所以我们选择$$$r = 5$$$。
因此第一个测试用例的输出是 $$$[3, 4, 5]$$$。