この問題は、累積和と二分探索を用いて解くことができます。

予め累積和 \(S_0 = 0\) , \(S_i = A_0 + A_1 + \ldots A_{i-1} \) を計算しておきます。これにより、\(A\) の任意の区間和を \(S_R - S_L = A_L + A_{L+1} + \ldots +A_{R-1}\) により \(O(1)\) で求めることができます。

累積和を用いて与えられた問題は以下のように書き換えられます：

• \(S_n - S_{L_i - 1}\) > \(\frac{1}{2} (S_{R_i}-S_{L_i-1})\) を満たす最小の正整数 \(n\) を出力せよ。

任意の \(i\) で \(A_i > 0\) であることから、 \(S_i\) は狭義単調増加であり、\(S_{R_i}-S_{L_i-1}\) は \(O(1)\) で求められるため、\(S_n - S_{L_i - 1}\) > \(\frac{1}{2} S_{R_i}-S_{L_i-1}\) となる最小の正整数 \(n\) は二分探索により \(O(\log N)\) で求めることができます。したがって、 \(O(Q \log N)\) で全てのクエリに答えることができます。