AT_pakencamp_2024_day1_c One Half

给定长度为 $N$ 的数列 $A = (A_1, A_2, \ldots, A_N)$，以及 $Q$ 个整数对 $(L_i, R_i)$，其中 $1 \leq L_i \leq R_i \leq N$。对于每个 $i = 1,2,\ldots,Q$，请解决如下问题： - 从 $A$ 的第 $L_i$ 个元素开始，依次向后累加，当其和首次超过从 $L_i$ 到 $R_i$ 所有元素总和的一半时，输出使得 $$ \sum_{k=L_i}^{n} A_k > \frac{1}{2}\sum_{k=L_i}^{R_i} A_k $$ 的最小正整数 $n$。

输入通过标准输入给出，格式如下： > $N$ $A_1$ $A_2$ $\ldots$ $A_N$ $Q$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_Q$ $R_Q$

输出共 $Q$ 行。第 $i$ 行（$1 \leq i \leq Q$）输出第 $i$ 个问题的答案。

### 样例解释 1 例如当 $i=2$ 时，$\sum_{k=1}^3 A_k = 2 + 3 + 5 = 10$。 - 当 $n=1$ 时，$\sum_{k=1}^1 A_k = 2$，$2 \leq \frac{1}{2} \times 10$，不满足条件。 - 当 $n=2$ 时，$\sum_{k=1}^2 A_k = 5$，$5 \leq \frac{1}{2} \times 10$，不满足条件。 - 当 $n=3$ 时，$\sum_{k=1}^3 A_k = 10$，$10 > \frac{1}{2} \times 10$，满足条件。 因此输出 $3$。 ### 样例解释 2 请注意，当总和无法用 $32$ 位整数表示时要小心。 ### 数据范围 - $1 \leq N \leq 2 \times 10^5$ - $1 \leq Q \leq 2 \times 10^5$ - $1 \leq A_i \leq 10^9$（$1 \leq i \leq N$） - $1 \leq L_i \leq R_i \leq N$（$1 \leq i \leq Q$） - 所有输入都是整数。 由 ChatGPT 5 翻译