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

My submissions

Announcements

5B. Swap Parities

Input

Output

Samples

5B. Swap Parities

Constraints

Input

Output

Samples

Constraints