Editorial: Reserved Reversals

The condition on a segment is about the parities of its minimum and maximum. Their sum is odd exactly when one of them is odd and the other is even.

The smallest useful segment has length $2$. If two adjacent elements have different parity, then the minimum and maximum of this length-$2$ segment also have different parity, so we may reverse the segment. Reversing a length-$2$ segment is just swapping the adjacent elements.

Therefore:

Any adjacent odd-even pair can be swapped legally.

This already tells us a lot. Odd elements can pass through even elements freely, and even elements can pass through odd elements freely. So the exact positions of the parities are flexible.

However, these adjacent odd-even swaps preserve two relative orders:

• the relative order of all odd elements;
• the relative order of all even elements.

If the odd subsequence and the even subsequence are both already non-decreasing, then we are done. We can stably merge these two sorted subsequences into the globally sorted array, using only adjacent swaps between different parities.

So the real question is:

When can we change the relative order of two elements with the same parity?

Consider two values $x$ and $y$ of the same parity, appearing in this order in the array, with

This is an inversion inside one parity subsequence. In any final non-decreasing array, $y$ must appear before $x$. Thus, at some point, an operation must reverse a segment containing both $x$ and $y$; otherwise their relative order would never change.

Look at such a segment. Since it contains both $x$ and $y$, and $x,y$ have the same parity:

• if the segment’s minimum has the same parity as $x,y$;
• and the segment’s maximum also has the same parity as $x,y$;

then the sum of the minimum and maximum is even, so the segment cannot be reversed.

For the reversal to be legal, one of the two extremes must have the opposite parity. Since the segment already contains $y$ and $x$, this can happen only in one of two ways:

• the segment contains an opposite-parity value smaller than $y$;
• the segment contains an opposite-parity value larger than $x$.

So every same-parity inversion $x > y$ needs a helper of the opposite parity outside the interval $[y,x]$.

For example, if $x,y$ are odd, then we need an even value $< y$ or an even value $> x$ somewhere in the array.

This condition is necessary.

Now suppose we have a same-parity adjacent inversion inside a parity subsequence:

“Adjacent inside the parity subsequence” means that between $x$ and $y$ in the actual array there may be some elements, but all of those elements have the opposite parity. We can move those elements away using legal adjacent odd-even swaps, so locally we may arrange the pair as consecutive:

x y

Assume there is an opposite-parity helper $z < y$. Move $z$ immediately to the left of the pair, again using only legal adjacent odd-even swaps:

z x y

The segment $[z,x,y]$ is reversible: its minimum is $z$, its maximum is $x$, and they have different parity. After reversing, the local order becomes:

y x z

So $y$ has moved before $x$.

The case with a large helper is symmetric. If there is an opposite-parity helper $z > x$, arrange:

x y z

The segment is reversible because its minimum is $y$ and its maximum is $z$, with different parity. After reversal:

z y x

Again, the pair $x,y$ has been swapped.

Therefore, if every same-parity inversion has an opposite-parity helper outside its value interval, we can sort each parity subsequence by bubble-sort-style adjacent inversion swaps. Once both parity subsequences are sorted, we stably merge them into the fully sorted array using adjacent swaps between different parities.

So the condition is both necessary and sufficient.

It remains to check the condition efficiently.

Fix one parity, say odd. Let:

For every inversion $x > y$ inside the odd subsequence, we need:

Checking every pair would be too slow. But when scanning the array from left to right, suppose the current odd value is $y$, and let

If $\mathrm{mx} \le y$, then $y$ creates no inversion with previous odd values.

If $\mathrm{mx} > y$, then there is at least one inversion ending at $y$. The strongest one to check is:

Indeed:

• if $L < y$, then this same small even value helps all inversions $(x,y)$;
• if $R > \mathrm{mx}$, then $R > x$ for every previous odd value $x \le \mathrm{mx}$.

Thus all inversions ending at $y$ are fixable if and only if:

We perform this scan once for odd values, using even values as helpers, and once for even values, using odd values as helpers.

For each test case:

1. Check one parity $p$.
2. Let $\mathrm{oppMin}$ and $\mathrm{oppMax}$ be the minimum and maximum values of parity $1-p$.
3. Scan the array from left to right, considering only values $y$ with parity $p$.
4. Maintain $\mathrm{mx}$, the maximum previous value with parity $p$.
5. If $\mathrm{mx} > y$, then require:

6. Update $\mathrm{mx} = \max(\mathrm{mx}, y)$.
7. Repeat for the other parity.

If both checks pass, print YES; otherwise print NO.

If the opposite parity does not exist, then $\mathrm{oppMin}$ and $\mathrm{oppMax}$ should be treated as nonexistent. In that case, no same-parity inversion can be fixed, which is exactly what the condition says.

The model solution implements the two parity checks with a neat trick.

In one pass, it treats even values as helpers and scans inversions among odd values:

int L = INF, R = -INF;
for (int i = 0; i < N; i++) {
    if (A[i] % 2 == 0) {
        chmin(L, A[i]);
        chmax(R, A[i]);
    }
}

int ma = -INF;
for (int i = 0; i < N; i++) {
    if (A[i] % 2) {
        if (ma > A[i]) {
            ok &= (R > ma || L < A[i]);
        }
        chmax(ma, A[i]);
    }
}

Then it increments every value by $1$. This swaps the parity of every number, so the exact same code checks the other direction: original odd values become the helpers, and original even values become the scanned subsequence.

The values all increase by $1$, but inequalities such as $R > ma$ and $L < A[i]$ are unchanged in meaning.

Each parity check is a linear scan. Therefore each test case is solved in $O(n)$ time, and the total complexity over all test cases is:

The memory usage is $O(1)$ besides the input array.