Array Coloring

The first rule says adjacent cards in the original row must have different colors. Since the original row is a path, this completely forces the coloring pattern once the first card is chosen:

$$color(i) = (i \bmod 2) \oplus x$$

for some fixed bit $x$.

The second rule says that after sorting by value, consecutive values must also have different colors. Since the values are distinct and each $a_i$ is between $1$ and $n$, the array is a permutation of $1,2,\ldots,n$. So the sorted row is also a path:

$$1,2,3,\ldots,n$$

That rule forces:

$$color(\text{value } v) = (v \bmod 2) \oplus y$$

for some fixed bit $y$.

Now look at the actual card at position $i$, whose value is $a_i$. Both forced formulas must describe the same card, so:

$$(i \bmod 2) \oplus x = (a_i \bmod 2) \oplus y$$

Rearrange the constants to one side:

$$(i \bmod 2) \oplus (a_i \bmod 2) = x \oplus y$$

The right side is one fixed value for the whole array. Therefore, the condition is simple as hell: for every position $i$, the parity relationship between $i$ and $a_i$ must be identical.

That means either:

• every $a_i$ has the same parity as $i$, or
• every $a_i$ has the opposite parity from $i$.

If this holds, we can color by position parity, and the sorted order will automatically alternate too. If it does not hold, then two cards demand incompatible parity patterns, so no coloring can satisfy both paths.

Edge cases are boring in the best way. For $n=2$, the same check works. The values are guaranteed distinct and in $[1,n]$, so we do not need to handle duplicates or missing values.

Complexity per test case is:

$$O(n)$$

with $O(1)$ extra memory.