問題文

長さ 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)
• 入力は全て整数

入力例 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 bit整数に収まらない計算がある場合に注意してください。