Hints: Reserved Reversals

Start with the smallest operation you are always allowed to do. When can you swap two adjacent elements?

If two adjacent elements have different parity, then the segment of length $2$ has minimum and maximum of different parity, so their sum is odd. Therefore, any adjacent pair of different parity can be swapped.

Answer to Hint 1: Adjacent swaps between opposite parities are very powerful. They mean you can move odd elements through even elements, and even elements through odd elements.

But such swaps do not change the relative order of the odd elements among themselves, nor the relative order of the even elements among themselves. So ask: if we only used these length-$2$ swaps, when would sorting be possible?

Answer to Hint 2: Using only opposite-parity adjacent swaps, the array can be rearranged into any interleaving of:

• the odd elements in their original relative order;
• the even elements in their original relative order.

So if both the odd subsequence and the even subsequence are already non-decreasing, the answer is immediately YES: just stably merge the two sorted subsequences into the globally sorted array.

The real difficulty is: can a longer reversal change the order of two elements with the same parity?

Answer to Hint 3: Suppose two same-parity values $x$ and $y$ appear in this order, with $x > y$. In the final sorted array, $y$ must come before $x$, so at some moment an operation must reverse a segment containing both of them.

What must be true about that segment for the operation to be legal?

Answer to Hint 4: The segment contains $x$ and $y$, and $x,y$ have the same parity. Since $y < x$, if the segment’s minimum and maximum were both among values of this same parity range, then the minimum and maximum would have the same parity and the reversal would be illegal.

For the segment to be legal, one of its extremes must have the opposite parity:

• either there is an opposite-parity value smaller than $y$;
• or there is an opposite-parity value larger than $x$.

So a same-parity inversion $x > y$ can only be fixed if some opposite-parity value lies outside the interval $[y,x]$.

Answer to Hint 5: This gives a necessary condition:

For every inverted pair $x > y$ inside the odd subsequence, there must be an even value $< y$ or an even value $> x$.

Similarly, for every inverted pair $x > y$ inside the even subsequence, there must be an odd value $< y$ or an odd value $> x$.

Can this condition also be sufficient? Try to fix one adjacent inversion inside one parity subsequence.

Answer to Hint 6: Assume $x$ and $y$ are adjacent inside the current same-parity subsequence and $x > y$. There may be opposite-parity elements between them in the actual array, but those can be moved away using legal adjacent opposite-parity swaps.

So locally, you can arrange the relevant part to look like:

x y

If you have an opposite-parity helper $z < y$, move it to the left:

z x y

Now reversing this length-$3$ segment is legal, because its minimum is $z$ and its maximum is $x$, which have different parity. The result contains $y$ before $x$.

Answer to Hint 7: The case with a large helper is symmetric. If there is an opposite-parity helper $z > x$, move it to the right:

x y z

This segment is legal, because its minimum is $y$ and its maximum is $z$, which have different parity. Reversing it again puts $y$ before $x$.

Therefore, whenever an adjacent same-parity inversion $x > y$ has an opposite-parity helper outside $[y,x]$, you can swap that inversion.

Answer to Hint 8: Now think like bubble sort.

To sort the odd subsequence, repeatedly swap adjacent inverted odd pairs. To sort the even subsequence, do the same for even pairs. Each such adjacent inversion corresponds to some inverted pair from the original parity subsequence, and it is swappable exactly when an opposite-parity value lies outside its value interval.

So the whole problem reduces to checking all inversions inside the two parity subsequences.

Answer to Hint 9: Naively checking all inverted pairs inside a parity subsequence is too slow. But for a fixed current value $y$, among all previous same-parity values, only the largest previous value matters.

Let $\mathrm{mx}$ be the maximum previous value of the same parity. If $\mathrm{mx} \le y$, then $y$ creates no new inversion. If $\mathrm{mx} > y$, then the hardest inversion ending at $y$ is $(\mathrm{mx}, y)$.

Why is checking only $(\mathrm{mx}, y)$ enough?

Answer to Hint 10: Suppose $\mathrm{mx} > y$. If there is an opposite-parity value $< y$, then it helps every inverted pair $(x,y)$ with $x > y$.

If there is an opposite-parity value $> \mathrm{mx}$, then it is also $> x$ for every previous same-parity value $x \le \mathrm{mx}$.

So the condition for all inversions ending at $y$ is simply:

Putting it all together: Do the same check twice:

1. Check inversions inside the odd subsequence, using the minimum and maximum even values as possible helpers.
2. Check inversions inside the even subsequence, using the minimum and maximum odd values as possible helpers.

For one parity $p$:

• compute $\mathrm{oppMin}$ and $\mathrm{oppMax}$ among values of parity $1-p$;
• scan the array left to right, considering only values of parity $p$;
• keep $\mathrm{mx}$, the maximum seen so far in this parity;
• when the current value $y$ satisfies $\mathrm{mx} > y$, require $\mathrm{oppMin} < y$ or $\mathrm{oppMax} > \mathrm{mx}$.

If every required check passes for both parities, print YES; otherwise print NO.

This is $O(n)$ per test case.