長さ \(N\) の数列 \(C = (C_{1}, C_{2}, \dots , C_{N})\) を以下のように定義します。

• \(C_{i}\) は \(2A_{i} \leq A_{i + a}\) を満たす最小の整数 \(a\)。ただし、\(2A_{i} > A_{N}\) のときは \(C_{i} = N + 1 - i\)

\(i\) 番目のクエリの答えが \(k\) 以上であることと、以下の \(2\) つの条件を満たすことは同値です。

• \(2k \leq R_{i} - L_{i} + 1\)
• \(\max(C_{L_{i}}, C_{L_{i} + 1}, \dots , C_{L_{i} + k - 1}) \leq R_{i} - L_{i} + 1 - k\)

この \(2\) つの条件を用いて、クエリごとに答えを二分探索すれば良いです。

\(2\) つめの条件は Sparse Table を用いて、\(O(1)\) で判定することができます。よって、時間計算量は \(O((N + Q)\log(N))\) です。

c++ 実装例 140ms