配点 : 200 点
問題文
长度 小于或等于 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 开始依次相加时,和为第一个下标。 持仓量超过总仓位的一半,直至 R_i ,即 满足 \displaystyle\sum_{k=L_i}^{n} A_k > \frac{1}{2} \displaystyle\sum_{k=L_i}^{R_i} A_k 的最小正整数 打印第 n 请输出
制約
- 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)
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
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
4 2 3 5 7 4 1 2 1 3 2 4 1 4
出力例 1
2 3 3 3
例如 第 i=2 时, \displaystyle\sum_{k=1}^{3} A_k = 2 + 3 + 5 = 10 。
- n=1 时, \displaystyle\sum_{k=1}^{1} A_k = 2 捻, 2 \leq \frac{1}{2} \times 10 ,因此不满足条件。
- n=2 时, \displaystyle\sum_{k=1}^{2} A_k = 5 捻, 5 \leq \frac{1}{2} \times 10 ,因此不满足条件。
- n=3 时, \displaystyle\sum_{k=1}^{3} A_k = 10 捻, 10 > \frac{1}{2} \times 10 ,所以满足条件。
综上所述, 您可以获得 3 请输出
入力例 2
5 1000000000 1000000000 1000000000 1000000000 1000000000 1 1 5
出力例 2
3
总和是 正整数序列,使得 32 如果您的计算不适合位整数,请小心。