Reserved Reversals

The whole problem looks like one of those “ah yes, let’s just reverse stuff and pray” tasks. Don’t. The trick is to understand what can never happen.

Key invariant: when can two elements cross?

Two elements can change relative order only if some chosen reversed segment contains both of them. If every operation that contains them is forbidden, then their order is permanent.

So fix two values $x<y$ of the same parity.

Suppose that all values of the opposite parity lie inside the value interval $[x,y]$. Then any segment containing both $x$ and $y$ has:

• minimum with parity equal to parity of $x$,
• maximum with parity equal to parity of $y$,

and since $x,y$ have the same parity, the minimum and maximum also have the same parity. Thus $m(l,r)+M(l,r)\equiv 0 \pmod 2,$ so such a segment is never allowed.

That means this pair can never cross.

---

Which pairs are frozen?

Let $mn_0 = \min\{a_i : a_i \text{ even}\}, \quad mx_0 = \max\{a_i : a_i \text{ even}\},$ $mn_1 = \min\{a_i : a_i \text{ odd}\}, \quad mx_1 = \max\{a_i : a_i \text{ odd}\}.$

Assume both parities exist.

For parity $p$, define:

• low-$p$ values: parity $p$ and value $< mn_{1-p}$,
• high-$p$ values: parity $p$ and value $> mx_{1-p}$.

Why are these special?

Take a low-$p$ value $x$ and a high-$p$ value $y$. All values of the opposite parity lie between them in value, i.e. $x < mn_{1-p} \le \text{(all opposite-parity values)} \le mx_{1-p} < y.$ So $x$ and $y$ are exactly the frozen kind of pair above. They can never change their relative order.

That’s the “reserved” part. Those pairs are locked.

---

Are there any other obstacles?

Nope — that’s the entire game.

If two same-parity values are not a low/high pair, then there exists an opposite-parity value outside their interval. That opposite-parity value can serve as a catalyst, and with allowed reversals you can rearrange such pairs when needed. Opposite-parity adjacent swaps are trivially allowed anyway, because for length $2$ we just need the two values to have different parity.

So the only genuine invariant is:

For each parity, every low element must remain before every high element.

If the initial array violates that for some parity, then sorted order is impossible. If it doesn’t violate that, then all remaining inversions are fixable.

---

What if one parity is missing?

Then every segment has minimum and maximum of the same parity, so no operation is allowed at all.

So in that case the answer is simply whether the array is already non-decreasing.

No parity mix, no party. Very rude problem.

---

Final criterion

If the array contains both parities, then for each parity $p$:

• let opposite parity be $q=1-p$,
• low-$p$: values $< mn_q$,
• high-$p$: values $> mx_q$.

Scan the array from left to right. If you ever see a high-$p$ element, and later see a low-$p$ element, then answer is NO.

Do this for both parities. If neither scan fails, answer is YES.

---

Why the scan works

For a fixed parity $p$, all low-$p$ elements must come before all high-$p$ elements in every reachable array. So if the original array already has some high-$p$ before some low-$p$, you’re dead.

Conversely, if that bad pattern never appears, then the frozen order constraints are already consistent with the sorted array, and everything else is movable enough to finish the sort.

So the whole problem collapses to two simple one-pass checks.

---

Complexity

For each test case:

• find min/max of both parities: $O(n)$,
• do two scans: $O(n)$.

Total complexity is $O(n)$ per test case, and $O\left(\sum n\right)$ over all test cases.

Memory usage is $O(n)$ if you store the array, or $O(1)$ extra besides input storage.

Short, mean, and effective.