Odd Swap Sort

题意翻译

#### 题目大意 给定一个数列 $a_1,a_2,...,a_n$ 。 你可以执行若干次如下的操作： - 选择一个整数 $i\ (\ 1\leq i< n\ )$ ，如果 $a_i+a_{i+1}$ 为奇数，交换 $a_i$ 和 $a_{i+1}$ 。 问是否可以将该数列排序成单调不降数列。 #### 输入格式 第一行一个整数 $t\ (\ 1\leq t\leq 10^5\ )$ ，表示测试组数。 每组第一行一个整数 $n\ (\ 1\leq n\leq 10^5)$ ，表示数列的长度。 每组第二行 $n$ 个整数 $a_1,a_2,...,a_n\ (\ 1\leq a_i\leq 10^9\ )$ ，表示给定的数列。 可以保证 $t$ 组测试的 $n$ 的和不超过 $2·10^5$ 。 #### 输出格式 共 $t$ 行。 对于每组测试，如果你可以将该数列排序成单调不降数列，输出 ``Yes`` ；否则，输出 ``No`` 。 #### 样例解释 - 第一组测试，可以交换 $31$ 和 $14$ （ $31+14=45$ 是奇数）然后得到单调不降数列 $[1,6,14,31]$ 。 - 第二组测试，我们想要得到单调不降数列就一定要交换 $4$ 和 $2$ ，但这是不可能的，因为 $4+2=6$ 是偶数。 - 第三组测试，没有方法可以使其排序成单调不降数列。 - 第四组测试，该数列已经是单调不降数列了。

题目描述

You are given an array $ a_1, a_2, \dots, a_n $ . You can perform operations on the array. In each operation you can choose an integer $ i $ ( $ 1 \le i < n $ ), and swap elements $ a_i $ and $ a_{i+1} $ of the array, if $ a_i + a_{i+1} $ is odd. Determine whether it can be sorted in non-decreasing order using this operation any number of times.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 10^5 $ ) — the number of test cases. Description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the length of the array. The second line of each test case contains $ n $ integers $ a_1,a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the elements of the array. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, print "Yes" or "No" depending on whether you can or can not sort the given array. You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer).

输入输出样例

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

说明

In the first test case, we can simply swap $ 31 $ and $ 14 $ ( $ 31 + 14 = 45 $ which is odd) and obtain the non-decreasing array $ [1,6,14,31] $ . In the second test case, the only way we could sort the array is by swapping $ 4 $ and $ 2 $ , but this is impossible, since their sum $ 4 + 2 = 6 $ is even. In the third test case, there is no way to make the array non-decreasing. In the fourth test case, the array is already non-decreasing.