MEX Reordering

The whole problem is basically about whether we can stop both sides from having the same relationship with $0$ and $1$.

Start with the most important fact: if a segment does not contain $0$, its MEX is $0$. No ceremony, no hidden trick.

So if the array has no zeroes, then every nonempty prefix and every nonempty suffix has MEX $0$. Since $n \ge 2$, there is at least one split, and that split is bad. Therefore:

$$\text{cnt}_0 = 0 \implies \text{NO}.$$

Now suppose there is exactly one zero. For any split, that single zero is on exactly one side. The side without the zero has MEX $0$. The side with the zero has MEX at least $1$. So the two MEX values are always different. Therefore:

$$\text{cnt}_0 = 1 \implies \text{YES}.$$

Now suppose there are at least two zeroes. This is where a tempting but wrong thought shows up: maybe lots of repeated values make construction easier. Nope. If there is no $1$, then any segment containing a zero has MEX exactly $1$.

Take any ordering. Let the first zero be at position $p$ and the last zero be at position $q$, with $p < q$. Split right after position $p$. The prefix contains a zero, and the suffix also contains a zero. Since there is no $1$ anywhere, both sides have MEX $1$. That split is bad, so no ordering can work:

$$\text{cnt}_0 \ge 2 \text{ and } \text{cnt}_1 = 0 \implies \text{NO}.$$

The remaining case is:

$$\text{cnt}_0 \ge 1 \quad \text{and} \quad \text{cnt}_1 \ge 1.$$

Here we can explicitly build a valid order: put all zeroes first. The rest can be anything, but imagine sorted order if you like.

Check every split:

• If the split is inside the block of zeroes, then the prefix contains $0$ but no $1$, so its MEX is $1$. The suffix contains at least one $0$ and at least one $1$, so its MEX is at least $2$. Different.
• If the split is after all zeroes, then the suffix contains no $0$, so its MEX is $0$. The prefix contains $0$, so its MEX is at least $1$. Different.

That covers all splits. So the final condition is simply:

$$\boxed{\text{YES iff } \text{cnt}_0 > 0 \text{ and } (\text{cnt}_0 = 1 \text{ or } \text{cnt}_1 > 0)}$$

We do not actually need to output the reordering, only whether it exists.

Complexity is $O(n)$ per test case, with $O(1)$ extra memory. Tiny constraints, tiny solution. Love when the problem folds like cheap cardboard.