辞書順で小さい方から \(L, \dots, R\) 番目の整数組 \((l, r)\) を \(l\) の値ごとに分類します。

• \((a, b), \dots, (a, N)\)
• \((a+1, a+2), \dots, (a, N)\)

\(\qquad \vdots\)

• \((a+k, a+k+ 1), \dots, (a+k, N)\)
• \((a+k+1, a+k+2), \dots, (a+k+1, c)\)

例えば \(N = 6, L = 3, R = 13\) の場合について、辞書順で小さい方から \(L, \dots, R\) 番目の整数組 \((l, r)\) に色をつけると以下の図のようになります。なお、全ての \(l + 1 \leq i \leq N\) について \((l, i)\) に色がつけられるならば \(l\) 行目は赤色で、それ以外の組については青色で示してます。

青色で示された整数組の個数は \(O(N)\) です。これらについては愚直に操作を行っても実行時間制限に間に合います。

赤色で示された整数組については最大で \(\Theta (N^2)\) 個の組があるため、愚直に操作することはできません。そこで、ある行に対応する操作を全て行ったときにどのように変化するかに注目しましょう。

数列 \((1, 2, \dots, N)\) に対し、\(i=2, \dots, N\) の順に \((1, i)\) に対応する操作を行うと \((N, 1, 2, \dots, N-1)\) となります。よって、\(n = 1, \dots, k\) の順に、次のような操作を行えばよいです。

• 数列の末尾の要素を取り出し、第 \(a+n\) 項の直前の位置に挿入する。

操作の一例を以下に示します。

結局、赤色で示された組に対する操作を全て行うことは、\(A_{a+1} \dots, A_N\) を逆順に並べ替えたあと、\(A_{a+k+1}, \dots, A_N\) をもう一度逆順に並べ替えるということと同じです。

以上により、次のステップを順に行うことでこの問題を \(O(N)\) で解くことができます。

• \(a, b, k, c\) の値を求める。ここで、操作すべき組 \((l, r)\) 全てに対して \(l = a\) が成り立つならば、愚直に操作を行い、以降のステップは無視する。
• \((a, b), \dots, (a, N)\) に対し愚直に操作を行う。
• \(A_{a+1} \dots, A_N\) を逆順に並べ替えたあと、\(A_{a+k+1}, \dots, A_N\) をもう一度逆順に並べ替える
• \((a + k + 1, a + k + 2), \dots, (a+k+1, c)\) に対し愚直に操作を行う。

実装例 (C++)