← 返回题目列表

Codeforces · 1851/B

B. 奇偶校验排序

中文机器翻译题面 查看原题

您有一个长度为 $$$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 \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$$$。

输出

对于每个测试用例,在单独的行上输出:

- 如果可以通过对数组应用多次操作来对数组进行排序,则为 YES;
- 否则不。

在任何情况下都可以输出 YES 和 NO(例如,字符串 yEs、yes、Yes 和 YES 将被识别为肯定响应)。

示例

输入 #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

输出 #1

YES
YES
NO
NO
YES
NO

注意

第一个测试用例在问题陈述中进行了解释。