\(R - L < L\) の場合

常に Yes です。

\(N = R\) の場合、\(A\) の前半 \(L\) 個の要素を消せば良いです。

\(P = (R - L, N - 1, N - 2, \dots, R - L + 1)\) とすると、\(i = 0\) のときの操作を除き、常に先頭を削除するので、前半の要素を削除していることになります。最初の操作も \(R - L < L\) であることから前半の要素を削除できています。よって、この順列は条件を満たすのでこれを出力すれば良いです。

\(R < N\) のときも、\(P_{0} = N - 1\) とすることで \(N - 1\) のケースに帰着できます。よって、\(P = (N - 1, N - 2, \dots, R) + (R - L) + (R - 1, R - 2, \dots, R - L + 1)\) とすれば良いです。

\(L \leq R - L\) の場合

\(x, y\) を \(x = L, y = N - R\) とします。これは、\(A\) の前半 \(x\) 個と後半 \(y\) 個が邪魔であることを表します。

\(0\leq a<y\) を満たす整数 \(a\) を選び、\((N - a - 1, N - 1, N - 2,\dots, N - a)\) と操作すると、 後半の要素を \(1\) つ減らし、前半の要素を \(a\) 個減らすことができます。よって、\(x' = x - a, y' = y - 1, N' = N - a - 1\) のケースに帰着できます。

このような操作を繰り返すことで、\(x\leq \dfrac{y(y - 1)}{2}\) であれば条件を満たす \(P\) を構築することができます。

逆に \(x>\dfrac{y(y - 1)}{2}\) であれば条件を満たす \(P\) が存在しないことが示せるので、そのようなときは No を出力すれば良いです。

実装例

実装例 C++

実装例 pypy

---

No の場合の証明

\(L\leq R - L\) かつ \(\frac{(N - R)(N - R - 1)}{2} < L\) であるとき No であることの証明をします。

\(R=N\) のときは \(L\leq R - L\) であることから、最初に消す要素が \(L\) 以上 \(N\) 未満であるため No となります。以降、\(R\neq N\) であると仮定します。

変数 \(x, y\) を \(x = L, y = N - R\) と初期化します。これは、\(A\) の前半 \(x\) 個と後半 \(y\) 個が邪魔であることを意味します。

\(L\leq R - L\) であることから、前半の要素を消すには \(|A|\leq P_{i}\) であることが必要です。 \(i\) 回目の操作で前半の要素を消すには \(j<i\) かつ \(P_{j}<P_{i}\) であるような \(j\) が存在することが必要です。

このことを踏まえ、\(i = 0, 1,\dots, N - (R - L) - 1\) の順に以下の操作をすることにします。

• 以下の行動 \(1,2\) のうち、いずれかを選んで行う。
  • 行動 \(1\) : \(x\) を \(1\) 減らす(前半の要素を消すことに対応)。これは \(P_{j}<P_{i}\) かつ \(j < i\) であるような \(j\) が存在するときのみ行える。
  • 行動 \(2\) : \(y\) を \(1\) 減らす(後半の要素を消すことに対応)。これは \(R - L + x\leq P_{i}\) であるときのみ行える。

このとき最終的な \(x, y\) を \((x, y) = (0, 0)\) にできることが答えが存在することに必要です。\(x\) が負になる操作をしたとき、\(x\leq 0\) であるときに行動 \(1\) をした操作を行動 \(2\) に置き換えても \((N - (R - L))\) 回の操作を完遂できるため、\(x\) の最小化をすることを考えます。

\(x\) の最小化を目指していてかつ \(x\) を減らした方が行動 \(2\) が行いやすいため、行動 \(1\) を行えるなら行動 \(1\) を行うとして良いです。

行動 \(2\) を行った \(P_{i}\) を並べた列を \(Q = (Q_{0}, Q_{1}, \dots, Q_{|Q| - 1})\) とします。この \(Q\) は単調減少であるとして良いです。

\(Q\) が単調減少であるとき、\(Q\) について、以下が成り立ちます。

• \(R\leq Q_{0}\)
• \(Q_{i} \leq Q_{i + 1} + (N - R - 1 - i)\)

\(R\leq Q_{0}\) に関しては、\(x = L\) で初期化されているからです。\(Q_{i}\) の操作をした後、\(Q_{i} < z\) を満たす整数 \(z\) に対して \(P_{i} = z\) として操作を行うと、\(x = L - (N - 1 - Q_{i} - i)\) とできるためです。

よって、\(|Q|\leq N - R\) となり、\(Q\) の末尾の要素は \(R - \dfrac{(N - R - 1)(N - R)}{2}\) 以上になります。

ここで \(\frac{(N - R)(N - R - 1)}{2} < L\) であることから、\(R - L<Q_{|Q| - 1}\) が成り立ちます。よって、\(P_{i} = R - L\) が成り立つ \(i\) について、行動 \(1\) を行うことになりますが、これはできません。よって、最終的な \(x\) を \(0\) 以下にすることはできません。

条件を緩和した状態でも条件を満たす \(P\) が存在しないことから、答えは常に No となります。