CF1638B.Odd Swap Sort

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 \lt 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.

给你一个数组 $a_1, a_2, \dots, a_n$。你可以对该数组执行若干次操作。每次操作中，你可以选择一个整数 $i$（满足 $1 \le i \lt n$），当且仅当 $a_i + a_{i+1}$ 为奇数时，交换数组中的元素 $a_i$ 和 $a_{i+1}$。

判断是否可以通过任意多次上述操作，将该数组排序为非递减序列。

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$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

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).

对于每个测试用例，根据能否对给定数组进行排序，输出“Yes”或“No”。

您可以以任意大小写形式输出每个字母（例如，“YES”、“Yes”、“yes”、“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.

在第一个测试用例中，我们只需交换 $31$ 和 $14$（因为 $31 + 14 = 45$ 是奇数），即可得到非递减数组 $[1,6,14,31]$。

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

在第三个测试用例中，无法使数组变为非递减。

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