オンラインで \(\mathrm{O}(N\log N + Q\log^2N)\) で解くこともできます。

\(r_i\) を、\(i < j, A_i < A_j\) を満たす \(j\) の最小値と定義します。（そのような \(j\) が存在しない場合 \(N\) とします。）

クエリが一個のとき、以下のアルゴリズムを用いて \(\mathrm{O}(N)\) で解くことができます。

• \(\mathrm{pos}=L_i,\mathrm{ans} = 1\) で初期化する。
• \(r_{\mathrm{pos}} \leq R_i\) を満たす限り、\(\mathrm{pos}\) を \(r_{\mathrm{pos}}\) で置き換え、 \(\mathrm{ans}\) に \(1\) を加算する。

最終的な \(\mathrm{ans}\) がクエリの答えになることは明らかです。

これを複数のクエリに対応させるためには、ダブリングを用いれば良いです。 各クエリでは \(x\) 回の置き換え後 \(\mathrm{pos}\leq R_i\) を満たすかについて \(x\) を二分探索することで、\(\mathrm{O}(N\log N + Q\log^2N)\) で解けます。また、ダブリングを直接用いて \(\mathrm{O}(N\log N + Q\log N)\) で解くこともできます。（この解法は shiomusubi496 さんに教えていただきました。）