Locked Out

We want minimum deletions, so do the less annoying version:

find the maximum number of elements we can keep.

Then the answer is $n-best$.

A kept array is bad only if there are two kept original positions $i<j$ with

$a_j-a_i=1.$

So an earlier $x$ and a later $x+1$ cannot both survive.

Sort the elements

Turn each element into a pair $(a_i,i)$, where $i$ is its original position.

Process pairs by:

1. value increasing,
2. position decreasing when values are equal.

So all copies of one value are processed from right to left.

Let $dp$ for occurrence $(x,i)$ mean:

the maximum size of a valid kept set whose last processed kept pair is $(x,i)$.

Last means last in this sorted order, not last in the original array.

Now compute the transition for current pair $(x,i)$.

Previous value at most $x-2$

Always safe. A value at most $x-2$ cannot differ from $x$ by exactly $1$.

So we can use:

$1 + best[value <= x-2].$

Previous value $x$

Also safe. Equal values do not conflict.

Because equal values are processed by decreasing position, repeatedly extending inside the same value just keeps more copies of $x$ from right to left. Nothing illegal happens.

So we can use:

$1 + best[value = x].$

Previous value $x-1$

This is the only spicy case.

If we keep $(x-1,j)$ and then keep $(x,i)$, we must avoid $j<i$, because that would put an earlier $x-1$ before a later $x$.

So we need:

$j>i.$

Thus we can use:

$1 + best[value = x-1, position > i].$

That is the whole DP. No secret fourth case hiding under the bed.

Why the decreasing tie-break matters

For one fixed value, positions are processed from right to left.

If a DP state for value $x-1$ ends at position $j$, then every selected occurrence of value $x-1$ inside that state has position at least $j$. Therefore, if $j>i$, all selected $x-1$ occurrences are after the current $x$, so appending current $x$ is safe.

Without this tie-break, the DP would start lying to your face.

Implementation

Store pos[x]: all positions where value $x$ appears, in increasing order.

Process values $x=1..n. For each value, process pos[x]` from back to front, which is decreasing position.

Maintain:

• prefixBest[v]: maximum DP over all processed values at most v.
• sameBest: maximum DP already computed for current value x.
• suf[x][k]: maximum DP among occurrences pos[x][k], pos[x][k+1], ....

For current position i = pos[x][k]:

• start with cur = 1;
• if x >= 2, try prefixBest[x - 2] + 1;
• try sameBest + 1;
• if x > 1, binary search in pos[x - 1] for the first position greater than i, then use the suffix maximum from there.

After finishing all occurrences of value x, build suf[x] from the computed DP values and set:

$prefixBest[x] = max(prefixBest[x-1], bestForValueX).$

Correctness proof

Take any valid kept set and sort its elements by the same rule: value increasing, decreasing position inside equal values.

Look at the final kept pair $(x,i)$ in that order. The previous kept pair, if it exists, must have value at most $x-2$, exactly $x$, or exactly $x-1$.

If it is at most $x-2$, appending $(x,i)$ is always safe. If it is $x$, appending is also safe. If it is $x-1$, validity forces its position to be greater than $i$; otherwise the original array would contain a forbidden earlier $x-1$ and later $x$.

So every valid solution is covered by one of our transitions.

Conversely, every transition we allow is valid:

• value gap at least $2$ cannot create a bad pair with current $x$;
• equal values cannot create a bad pair;
• value $x-1$ is allowed only from positions greater than $i$, so those $x-1$ elements are after current $x$ in the original array.

Therefore the DP computes the maximum number of kept elements.

Finally, output:

$n-best.$

Complexity

Each occurrence is processed once, and each occurrence does one binary search in the previous value's position list.

Total complexity is $O(n log n)$ per test case, with $O(n)$ memory.

Quadratic DP gets cooked here; this one actually passes.