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 $ から順に足していくとき、その和が初めて添字 $ R_i $ までの総和の半分を超える位置、つまり $ \displaystyle\sum_{k=L_i}^{n} A_k > \frac{1}{2} \displaystyle\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 $ 番目の問題の答えを出力せよ。

### Sample Explanation 1 例えば $ 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 $ を出力してください。 ### Sample Explanation 2 総和が $ 32 $ bit整数に収まらない計算がある場合に注意してください。 ### Constraints - $ 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 $ ) - 入力は全て整数