When \(R - L < L\)

The answer is always Yes.

When \(N = R\), we need to remove the first \(L\) elements of \(A\).

If we set \(P = (R - L, N - 1, N - 2, \dots, R - L + 1)\), except for the operation when \(i = 0\), we always remove the first element, so we are removing elements from the first half. The first operation can also remove an element from the first half since \(R - L < L\). Therefore, this permutation satisfies the condition and we can output it.

When \(R < N\), by setting \(P_0 = N - 1\), we can reduce it to the case \(N - 1\). Therefore, we can set \(P = (N - 1, N - 2, \dots, R) + (R - L) + (R - 1, R - 2, \dots, R - L + 1)\).

When \(L \leq R - L\)

Let \(x, y\) be \(x = L, y = N - R\). This represents that the first \(x\) and last \(y\) elements of \(A\) are obstacles.

By choosing an integer \(a\) satisfying \(0 \leq a < y\) and performing operations \((N - a - 1, N - 1, N - 2, \dots, N - a)\), we can reduce the last elements by \(1\) and the first elements by \(a\). Therefore, we can reduce it to the case \(x' = x - a, y' = y - 1, N' = N - a - 1\).

By repeating such operations, if \(x \leq \dfrac{y(y - 1)}{2}\), we can construct \(P\) that satisfies the condition.

Conversely, if \(x > \dfrac{y(y - 1)}{2}\), it can be shown that no \(P\) satisfying the condition exists, so we should output No in such cases.

Implementation Examples

C++ Implementation

PyPy Implementation

---

Proof for the No case

We prove that the answer is No when \(L \leq R - L\) and \(\dfrac{(N - R)(N - R - 1)}{2} < L\).

When \(R = N\), since \(L \leq R - L\), the first element to remove is at least \(L\) and less than \(N\), so the answer is No. Hereafter, we assume \(R \neq N\).

Initialize variables \(x, y\) as \(x = L, y = N - R\). This means that the first \(x\) and last \(y\) elements of \(A\) are obstacles.

Since \(L \leq R - L\), to remove an element from the first half, we need \(|A| \leq P_i\). To remove an element from the first half in the \(i\)-th operation, there must exist \(j\) such that \(j < i\) and \(P_j < P_i\).

With this in mind, for \(i = 0, 1, \dots, N - (R - L) - 1\) in order, we perform the following operations:

• Choose one of the following actions 1 or 2:
  • Action 1: Decrease \(x\) by \(1\) (corresponding to removing an element from the first half). This can only be done when there exists \(j\) such that \(P_j < P_i\) and \(j < i\).
  • Action 2: Decrease \(y\) by \(1\) (corresponding to removing an element from the last half). This can only be done when \(R - L + x \leq P_i\).

It is necessary that we can make the final \((x, y) = (0, 0)\) for a solution to exist. When an operation makes \(x\) negative, since we can replace an operation that performed action 1 when \(x \leq 0\) with action 2 and still complete \((N - (R - L))\) operations, we consider minimizing \(x\).

Since we aim to minimize \(x\) and reducing \(x\) makes action 2 easier to perform, we should perform action 1 whenever it’s possible.

Let \(Q = (Q_0, Q_1, \dots, Q_{|Q| - 1})\) be the sequence of \(P_i\) values for which we performed action 2. We can assume this \(Q\) is monotonically decreasing.

When \(Q\) is monotonically decreasing, the following holds for \(Q\):

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

Regarding \(R \leq Q_0\), this is because \(x = L\) is initialized. After performing the operation \(Q_i\), for an integer \(z\) satisfying \(Q_i < z\), if we perform the operation with \(P_i = z\), we can achieve \(x = L - (N - 1 - Q_i - i)\).

Therefore, \(|Q| \leq N - R\), and the last element of \(Q\) is at least \(R - \dfrac{(N - R - 1)(N - R)}{2}\).

Since \(\dfrac{(N - R)(N - R - 1)}{2} < L\), we have \(R - L < Q_{|Q| - 1}\). Therefore, for \(i\) such that \(P_i = R - L\), we would perform action 1, but this is impossible. Hence, we cannot make the final \(x\) equal to or less than \(0\).

Since no \(P\) satisfying the condition exists even under relaxed conditions, the answer is always No.