您有一个长度为 $$$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
注意
第一个测试用例在问题陈述中进行了解释。