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 there is no element of this same parity between $x$ and $y$ in that parity subsequence. In the actual array there may still be opposite-parity elements between them.

The important fact is slightly stronger than just “we can move an odd through an even”:

Using adjacent swaps between different parities, we can transform the array into any interleaving of the odd subsequence and the even subsequence, while preserving the order inside each subsequence.

This is the usual property of adjacent swaps between two colors: they can change the binary pattern of parities arbitrarily, but they cannot reorder equal colors.

So, when we use an opposite-parity helper $z$, we are not claiming that $z$ can jump over elements of its own parity. It cannot. Instead, we choose a convenient interleaving of the two parity subsequences.

Assume there is an opposite-parity helper $z < y$. We can choose an interleaving where all opposite-parity elements before $z$ in their own subsequence appear before the local block, then $z$ appears, then the adjacent same-parity pair $x,y$, and all opposite-parity elements after $z$ appear after the block. Locally, we get:

z x y

This arrangement preserves the order of the opposite-parity subsequence; it only changes how the two parity subsequences are interleaved.

Now 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$, choose an interleaving where $z$ is immediately after the pair:

x y z

Again, all opposite-parity elements before $z$ in their own subsequence are placed before this block, and all opposite-parity elements after $z$ are placed after it, so no same-parity order is violated.

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.