CF1933E.Turtle vs. Rabbit Race: Optimal Trainings

Isaac begins his training. There are $n$ running tracks available, and the $i$-th track ($1 \le i \le n$) consists of $a_i$ equal-length sections.

Given an integer $u$ ($1 \le u \le 10^9$), finishing each section can increase Isaac's ability by a certain value, described as follows:

• Finishing the $1$-st section increases Isaac's performance by $u$.
• Finishing the $2$-nd section increases Isaac's performance by $u-1$.
• Finishing the $3$-rd section increases Isaac's performance by $u-2$.
• $\ldots$
• Finishing the $k$-th section ($k \ge 1$) increases Isaac's performance by $u+1-k$. (The value $u+1-k$ can be negative, which means finishing an extra section decreases Isaac's performance.)

You are also given an integer $l$. You must choose an integer $r$ such that $l \le r \le n$ and Isaac will finish each section of each track $l, l + 1, \dots, r$ (that is, a total of $\sum_{i=l}^r a_i = a_l + a_{l+1} + \ldots + a_r$ sections).

Answer the following question: what is the optimal $r$ you can choose that the increase in Isaac's performance is maximum possible?

If there are multiple $r$ that maximize the increase in Isaac's performance, output the smallest $r$.

To increase the difficulty, you need to answer the question for $q$ different values of $l$ and $u$.

艾萨克开始他的训练。目前有 $n$ 条跑道可供使用，其中第 $i$ 条跑道（$1 \le i \le n$）由 $a_i$ 个等长的路段组成。

给定一个整数 $u$（$1 \le u \le 10^9$），完成每个路段将使艾萨克的能力提升某一特定数值，具体规则如下：

• 完成第 $1$ 个路段，使艾萨克的表现提升 $u$；
• 完成第 $2$ 个路段，使艾萨克的表现提升 $u-1$；
• 完成第 $3$ 个路段，使艾萨克的表现提升 $u-2$；
• $\ldots$
• 完成第 $k$ 个路段（$k \ge 1$），使艾萨克的表现提升 $u+1-k$。（注意：$u+1-k$ 可能为负数，即额外完成一个路段反而会降低艾萨克的表现。）

同时给定一个整数 $l$。你必须选择一个整数 $r$，满足 $l \le r \le n$，使得艾萨克完成从第 $l$ 条到第 $r$ 条（含）所有跑道上的每一个路段（即总共完成 $\sum_{i=l}^r a_i = a_l + a_{l+1} + \ldots + a_r$ 个路段）。

请回答以下问题：应选择哪个 $r$，才能使艾萨克的表现提升值达到最大？

若存在多个 $r$ 均可使表现提升值达到最大，请输出其中最小的 $r$。

为增加难度，你需要对 $q$ 组不同的 $(l, u)$ 参数分别回答该问题。

The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The descriptions of the test cases follow.

The first line contains a single integer $n$ ($1 \le n \le 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^4$).

The third line contains a single integer $q$ ($1 \le q \le 10^5$).

The next $q$ lines each contain two integers $l$ and $u$ ($1 \le l \le n, 1 \le u \le 10^9$) — the descriptions to each query.

The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. The sum of $q$ over all test cases does not exceed $2 \cdot 10^5$.

输入的第一行包含一个整数 $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$。

For each test case, output $q$ integers: the $i$-th integer contains the optimal $r$ for the $i$-th query. If there are multiple solutions, output the smallest one.

对于每个测试用例，输出 $q$ 个整数：第 $i$ 个整数为第 $i$ 个查询的最优 $r$。若存在多个解，则输出最小的那个。

For the $1$-st query in the first test case:

• By choosing $r = 3$, Isaac finishes $a_1 + a_2 + a_3 = 3 + 1 + 4 = 8$ sections in total, hence his increase in performance is $u+(u-1)+\ldots+(u-7)=8+7+6+5+4+3+2+1 = 36$.
• By choosing $r = 4$, Isaac finishes $a_1 + a_2 + a_3 + a_4 = 3 + 1 + 4 + 1 = 9$ sections in total, hence his increase in performance is $u+(u-1)+\ldots+(u-8)=8+7+6+5+4+3+2+1+0 = 36$.

Both choices yield the optimal increase in performance, however we want to choose the smallest $r$. So we choose $r = 3$.

For the $2$-nd query in the first test case, by choosing $r = 4$, Isaac finishes $a_2 + a_3 + a_4 = 1 + 4 + 1 = 6$ sections in total, hence his increase in performance is $u+(u-1)+\ldots+(u-5)=7+6+5+4+3+2 = 27$. This is the optimal increase in performance.

For the $3$-rd query in the first test case:

• By choosing $r = 5$, Isaac finishes $a_5 = 5$ sections in total, hence his increase in performance is $u+(u-1)+\ldots+(u-4)=9+8+7+6+5 = 35$.
• By choosing $r = 6$, Isaac finishes $a_5 + a_6 = 5 + 9 = 14$ sections in total, hence his increase in performance is $u+(u-1)+\ldots+(u-13)=9+8+7+6+5+4+3+2+1+0+(-1)+(-2)+(-3)+(-4) = 35$.

Both choices yield the optimal increase in performance, however we want to choose the smallest $r$. So we choose $r = 5$.

Hence the output for the first test case is $[3, 4, 5]$.

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

• 若选择 $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$ 次查询，若选择 $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$ 次查询：

• 若选择 $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]$。