Deranged Deletions

We need delete some elements so the remaining array $d$ is a derangement under this custom definition: make a sorted copy $c$, and require

$d_i \ne c_i$

for every position $i$.

The key thing: after deletions, the remaining array is a subsequence of the original array. We do not get to reorder anything.

Length 1 is useless

If $d=[x]$, then its sorted copy is also $[x]$. So $d_1=c_1$, meaning it is never a derangement.

So the smallest possible useful answer has length $2$.

Analyze length 2

Take some subsequence $[x,y]$.

Its sorted version is:

$[\min(x,y), \max(x,y)]$

There are three cases:

• If $x<y$, then $[x,y]$ is already sorted, so both positions match. Bad.
• If $x=y$, then sorting changes nothing. Bad.
• If $x>y$, then sorted version is $[y,x]$. Now position $1$ has $x \ne y$, and position $2$ has $y \ne x$. Good.

So any decreasing pair $x>y$ immediately gives a valid answer of length $2$. That's the whole trick. No need to build some giant fancy subsequence. This is an 800, not a tax form.

When is it impossible?

If there is no pair $i<j$ with $a_i>a_j$, then the array is non-decreasing.

And every subsequence of a non-decreasing array is also non-decreasing. That means every possible remaining array is already sorted, so its sorted copy is identical to itself. Therefore every position matches, and it cannot be a derangement.

So the condition is exactly:

• If there exists an inversion $i<j$ with $a_i>a_j$, print YES, then print the subsequence $[a_i,a_j]$.
• Otherwise, print NO.

Algorithm

For each test case:

1. Read $n$ and the array.
2. Check all pairs $(i,j)$ with $i<j$.
3. If $a_i>a_j$, output:
   • YES
   • 2
   • a_i a_j
4. If no such pair exists, output NO.

The constraints are tiny: $n\le 100$, so $O(n^2)$ is completely fine.

Correctness proof

Suppose the algorithm prints YES. It found indices $i<j$ with $a_i>a_j$ and outputs $d=[a_i,a_j]$. Since $i<j$, this is a valid subsequence. Its sorted copy is $[a_j,a_i]$, because $a_i>a_j$. Thus $d_1=a_i\ne a_j=c_1$ and $d_2=a_j\ne a_i=c_2$. Therefore $d$ is a derangement.

Suppose the algorithm prints NO. Then there is no pair $i<j$ such that $a_i>a_j$, so $a$ is non-decreasing. Every subsequence of a non-decreasing array is also non-decreasing. Therefore any remaining array equals its sorted copy, so at least one position matches; in fact, every position matches. Hence no valid non-empty derangement can be formed.

Therefore the algorithm is correct.