← 返回题目列表

AtCoder · pakencamp_2024_day1_c

C. 一半

中文机器翻译题面 查看原题

配点 : 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 如果您的计算不适合位整数,请小心。