← 返回题目列表

Codeforces · 1638/B

B. 奇数交换排序

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

给你一个数组 $$$a_1, a_2, \dots, a_n$$$。您可以对数组执行操作。在每个操作中,您可以选择一个整数 $$$i$$$ ($$$1 \le i < n$$$),如果 $$$a_i + a_{i+1}$$$ 是奇数,则交换数组的 $$$a_i$$$ 和 $$$a_{i+1}$$$ 元素。

确定是否可以多次使用此操作按非降序排序。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数组的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组的元素。

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

输出

对于每个测试用例,根据是否可以对给定数组进行排序来打印“是”或“否”。

您可以在任何情况下打印每个字母(例如,“YES”、“Yes”、“yes”、“yEs”都将被识别为肯定答案)。

示例

输入 #1

4
4
1 6 31 14
2
4 2
5
2 9 6 7 10
3
6 6 6

输出 #1

Yes
No
No
Yes

注意

在第一个测试用例中,我们可以简单地交换$$$31$$$和$$$14$$$($$$31 + 14 = 45$$$,这是奇数)并获得非递减数组$$$[1,6,14,31]$$$。

在第二个测试用例中,我们对数组进行排序的唯一方法是交换 $$$4$$$ 和 $$$2$$$,但这是不可能的,因为它们的总和 $$$4 + 2 = 6$$$ 是偶数。

在第三个测试用例中,没有办法使数组不减。

在第四个测试用例中,数组已经是非递减的。