CF1851B.Parity Sort

You have an array of integers $a$ of length $n$. You can apply the following operation to the given array:

• Swap two elements $a_i$ and $a_j$ such that $i \neq j$, $a_i$ and $a_j$ are either both even or both odd.

Determine whether it is possible to sort the array in non-decreasing order by performing the operation any number of times (possibly zero).

For example, let $a$ = [$7, 10, 1, 3, 2$]. Then we can perform $3$ operations to sort the array:

1. Swap $a_3 = 1$ and $a_1 = 7$, since $1$ and $7$ are odd. We get $a$ = [$1, 10, 7, 3, 2$];
2. Swap $a_2 = 10$ and $a_5 = 2$, since $10$ and $2$ are even. We get $a$ = [$1, 2, 7, 3, 10$];
3. Swap $a_4 = 3$ and $a_3 = 7$, since $3$ and $7$ are odd. We get $a$ = [$1, 2, 3, 7, 10$].

你有一个长度为 $n$ 的整数数组 $a$。你可以对给定数组执行以下操作：

• 交换两个元素 $a_i$ 和 $a_j$，其中 $i \neq j$，且 $a_i$ 与 $a_j$ 要么均为偶数，要么均为奇数。

判断是否可以通过任意次数（包括零次）执行该操作，将数组排序为非递减顺序。

例如，设 $a = [7, 10, 1, 3, 2]$。那么我们可以通过 $3$ 次操作将数组排序：

1. 交换 $a_3 = 1$ 与 $a_1 = 7$，因为 $1$ 和 $7$ 均为奇数。得到 $a = [1, 10, 7, 3, 2]$；
2. 交换 $a_2 = 10$ 与 $a_5 = 2$，因为 $10$ 和 $2$ 均为偶数。得到 $a = [1, 2, 7, 3, 10]$；
3. 交换 $a_4 = 3$ 与 $a_3 = 7$，因为 $3$ 和 $7$ 均为奇数。得到 $a = [1, 2, 3, 7, 10]$。

The first line of input data contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The description of the test cases follows.

The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of array $a$.

The second line of each test case contains exactly $n$ positive integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the elements of array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

输入数据的第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 表示数组 $a$ 的长度。

每个测试用例的第二行包含恰好 $n$ 个正整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）—— 表示数组 $a$ 的元素。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case, output on a separate line:

• YES if the array can be sorted by applying the operation to it some number of times;
• NO otherwise.

You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as positive response).

对于每个测试用例，在单独的一行上输出：

• 如果可以通过对该数组执行若干次该操作使其变为有序，则输出 YES；
• 否则输出 NO。

YES 和 NO 的大小写不限（例如，字符串 yEs、yes、Yes 和 YES 均被视为肯定回答）。

The first test case is explained in the problem statement.

第一个测试用例在题目描述中已作解释。