Swap Parities - Repovive Standard Round 2 | Repovive

5B. Swap Parities

1000 pts2s256 MB

You are given an array $a$ of $n$ integers.

You can perform the following operation any number of times (possibly zero): Choose two adjacent elements $a_i$ and $a_{i+1}$ . If they have different parities (i.e., one is even and the other is odd), you can swap them.

Determine whether it is possible to sort the array in non-decreasing order using this operation.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$ .

Input

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} \text{Yes / No} \end{array} \right\} \times t

Samples

Input

Case 1

3
7 3 4

Case 2

3
3 4 7

Case 3

4
2 4 1 3

Case 4

2
4 2

Explanation

Case 1

We can only swap $3$ and $4$ to get $7, 4, 3$ , and then swap $7$ and $4$ to get $4, 7, 3$ . It is impossible to fully sort this array using the given operations.

Case 2

The array is already sorted in non-decreasing order, so no operations are needed.

Case 3

We can sort the array with the following operations:

Swap $4$ and $1$ (since they have different parities): $2, 1, 4, 3$
Swap $2$ and $1$ : $1, 2, 4, 3$
Swap $4$ and $3$ : $1, 2, 3, 4$

The array is now sorted.

Case 4

Both numbers are even, so we cannot swap them. Thus, it is impossible to sort the array.

Output

Case 1

No

Case 2

Yes

Case 3

Yes

Case 4

No

You are given an array $a$ of $n$ integers.

Determine whether it is possible to sort the array in non-decreasing order using this operation.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$ .

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

\left. \begin{array}{l} \text{Yes / No} \end{array} \right\} \times t

We can only swap $3$ and $4$ to get $7, 4, 3$ , and then swap $7$ and $4$ to get $4, 7, 3$ . It is impossible to fully sort this array using the given operations.

We can sort the array with the following operations:

Swap $4$ and $1$ (since they have different parities): $2, 1, 4, 3$
Swap $2$ and $1$ : $1, 2, 4, 3$
Swap $4$ and $3$ : $1, 2, 3, 4$

The array is now sorted.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

5B. Swap Parities

Input

Output

Samples

5B. Swap Parities

Constraints

Input

Output

Samples

Constraints