3876. Construct Uniform Parity Array II

The whole thing reduces to one comparison: the smallest odd value against the smallest even value. Subtracting an operand flips a number's parity only when that operand is odd — odd minus odd is even, even minus odd is odd — and the move is legal only when you take away something strictly smaller. Every parity flip therefore needs a smaller odd number already sitting in the array.