CF1933E Turtle vs. Rabbit Race: Optimal Trainings

艾萨克开始了他的训练。有 $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, l+1, \dots, r$ 条跑道的所有区间（即总共完成 $\sum_{i=l}^r a_i = a_l + a_{l+1} + \ldots + a_r$ 段区间）。 请回答如下问题：你能选择的 $r$ 使得艾萨克能力值的提升最大？如果有多个 $r$ 能使能力值提升最大，请输出最小的 $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 \times 10^5$。所有测试用例中 $q$ 的总和不超过 $2 \times 10^5$。

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

对于第一个测试用例的第 $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$。 对于第一个测试用例的第 $2$ 个询问，选择 $r=4$ 时，艾萨克完成了 $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$ 时，艾萨克完成了 $a_5=5$ 段区间，因此能力值提升为 $u+(u-1)+\ldots+(u-4)=9+8+7+6+5=35$。 - 选择 $r=6$ 时，艾萨克完成了 $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]$。 由 ChatGPT 4.1 翻译