给你一个数组 $$$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$$$ 是偶数。
在第三个测试用例中,没有办法使数组不减。
在第四个测试用例中,数组已经是非递减的。