Deletion Sort

The trick is the forced stop condition. You may delete only while the current array is not non-decreasing. Once it becomes non-decreasing, the game ends immediately. So the common thought "find the shortest non-decreasing subsequence" is the wrong rabbit hole. Tiny problem, tiny answer: either $n$ or $1$.

Let the initial array be $a$.

If $a$ is already non-decreasing, then the game checks the first rule before any deletion. The game ends right there, so no element can be removed. The answer is therefore $n$.

Now suppose $a$ is not non-decreasing. Then there exists an index $i$ such that

$a_i > a_{i+1}.$

Keep these two adjacent elements. Delete every other element first, in any order. During all those deletions, this same bad pair still appears in the remaining array, with $a_i$ before $a_{i+1}$, and since originally they were adjacent, nothing can sneak between them. Therefore the array is still not non-decreasing, so the game does not stop early.

Eventually the remaining array can be just

$[a_i, a_{i+1}],$

and this is still decreasing because $a_i > a_{i+1}$. Since the game has not ended yet, we are allowed to delete one of these two elements. After that, exactly one element remains.

A one-element array is always non-decreasing, so the game ends with $1$ element. We cannot end with $0$ elements, because after reaching length $1$, the game stops before another deletion is allowed. That is the whole thing. No DP, no greedy gymnastics, no fake complexity tax.

So:

$$\text{answer} = \begin{cases} n, & \text{if } a \text{ is initially non-decreasing},\\ 1, & \text{otherwise.} \end{cases}$$

Edge cases:

• $n=1$: the array is non-decreasing, so the answer is $1$.
• Already sorted arrays like $[1,2,2,5]$: answer is $n$, because no deletion can happen.
• Any unsorted array: answer is $1$, by preserving one adjacent inversion until the end.

Implementation just checks whether every $a_i \le a_{i+1}$. In C++, is_sorted(a.begin(), a.end()) does exactly that for non-decreasing order.

Complexity per test case is $O(n)$ time and $O(n)$ memory for the input array. With $n \le 10$, this is basically free.

Research checked: the official Codeforces statement, the official round editorial page whose B implementation uses exactly this sorted-check split, the public Codeforces status page showing accepted B submissions, and a short Codeforces explanation of the same $1$-or-$n$ observation.