CF 1851B - Parity Sort

You have an array of integers a of length n. You can apply the following operation to the given array:

Swap two elements ai and aj such that i≠j, ai and aj are either both even or both odd.

Determine whether it is possible to sort the array in non-decreasing order by performing the operation any number of times (possibly Zero).

For example, let a = [7,10,1,3,2]. Then we can perform 3 operations to sort the array:

Swap a3=1 and a1=7, since 1 and 7 are odd. We get a = [1,10,7,3,2];

Swap a2=10 and a5=2, since 10 and 2 are even. We get a = [1,2,7,3,10];

Swap a4=3 and a3=7, since 3 and 7 are odd. We get a = [1,2,3,7,10].

Input

The first line of input data contains a single integer t

 (1≤t≤104) — the number of test cases.

The description of the test cases follows.

The first line of each test case contains one integer n (1≤n≤2⋅105) — the length of array a.

The second line of each test case contains exactly n positive integers a1,a2,…,an (1≤ai≤109) — the elements of array a.

It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.

Output

For each test case, output on a separate line:

YES if the array can be sorted by applying the operation to it some number of times;

NO otherwise.

You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as positive response).

------------------------------------------------------------

您有一个长度为 n 的整数数组 a。 您可以对给定数组应用以下操作：

交换两个元素 ai 和 aj，使得 i≠j，ai 和 aj 要么都是偶数，要么都是奇数。

通过执行任意次数（可能为零）的操作，确定是否可以按非降序对数组进行排序。

例如，令 a = [7,10,1,3,2]。 然后我们可以执行 3 个操作来对数组进行排序：

交换 a3=1 和 a1=7，因为 1 和 7 是奇数。 我们得到 a = [1,10,7,3,2];

交换 a2=10 和 a5=2，因为 10 和 2 是偶数。 我们得到 a = [1,2,7,3,10];

交换 a4=3 和 a3=7，因为 3 和 7 是奇数。 我们得到 a = [1,2,3,7,10]。

输入

输入数据的第一行包含一个整数 t

  (1≤t≤104) — 测试用例的数量。

测试用例的描述如下。

每个测试用例的第一行包含一个整数 n (1≤n≤2⋅105) — 数组 a 的长度。

每个测试用例的第二行恰好包含 n 个正整数 a1,a2,…,an (1≤ai≤109) — 数组 a 的元素。

保证所有测试用例的 n 之和不超过 2⋅105。

输出

对于每个测试用例，在单独的行上输出：

如果可以通过对数组应用多次操作来对数组进行排序，则为 YES；

否则不行。

您可以在任何情况下输出 YES 和 NO（例如，字符串 yEs、yes、Yes 和 YES 将被识别为肯定响应）。

-----------------------------------

一开始用2个list去存储奇数跟偶数，然后根据顺序去判断是否成立，但是这种情况会超时，于是就换成了2个数组直接存储数据，然后排序其中一个数组，去跟之前那个数组去比较数字的奇偶性，这样还是会超时，真的是奇了怪了，于是把另一个数组的类型从int改成Integer，结果就过了，不懂为什么了，（可能是引用类型的原因）下面是代码：