题目描述

给定一个长度为 $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]$。

输入格式

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

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

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

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

保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出一行：

• 如果可以通过若干次操作将数组排序，输出 YES；
• 否则输出 NO。

你可以用任意大小写形式输出 YES 和 NO（例如 yEs, yes, Yes 和 YES 都会被识别为肯定回答）。

说明/提示

第一个测试用例的操作过程已在题目描述中给出。

由 ChatGPT 4.1 翻译

样例

6
5
7 10 1 3 2
4
11 9 3 5
5
11 3 15 3 2
6
10 7 8 1 2 3
1
10
5
6 6 4 1 6

YES
YES
NO
NO
YES
NO