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 的整數(shù)數(shù)組 a。 您可以對給定數(shù)組應用以下操作：

交換兩個元素 ai 和 aj，使得 i≠j，ai 和 aj 要么都是偶數(shù)，要么都是奇數(shù)。

通過執(zhí)行任意次數(shù)（可能為零）的操作，確定是否可以按非降序對數(shù)組進行排序。

例如，令 a = [7,10,1,3,2]。 然后我們可以執(zhí)行 3 個操作來對數(shù)組進行排序：

交換 a3=1 和 a1=7，因為 1 和 7 是奇數(shù)。 我們得到 a = [1,10,7,3,2];

交換 a2=10 和 a5=2，因為 10 和 2 是偶數(shù)。 我們得到 a = [1,2,7,3,10];

交換 a4=3 和 a3=7，因為 3 和 7 是奇數(shù)。 我們得到 a = [1,2,3,7,10]。

輸入

輸入數(shù)據(jù)的第一行包含一個整數(shù) t

? (1≤t≤104) — 測試用例的數(shù)量。

測試用例的描述如下。

每個測試用例的第一行包含一個整數(shù) n (1≤n≤2?105) — 數(shù)組 a 的長度。

每個測試用例的第二行恰好包含 n 個正整數(shù) a1,a2,…,an (1≤ai≤109) — 數(shù)組 a 的元素。

保證所有測試用例的 n 之和不超過 2?105。

輸出

對于每個測試用例，在單獨的行上輸出：

如果可以通過對數(shù)組應用多次操作來對數(shù)組進行排序，則為 YES；

否則不行。

您可以在任何情況下輸出 YES 和 NO（例如，字符串 yEs、yes、Yes 和 YES 將被識別為肯定響應）。

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

一開始用2個list去存儲奇數(shù)跟偶數(shù)，然后根據(jù)順序去判斷是否成立，但是這種情況會超時，于是就換成了2個數(shù)組直接存儲數(shù)據(jù)，然后排序其中一個數(shù)組，去跟之前那個數(shù)組去比較數(shù)字的奇偶性，這樣還是會超時，真的是奇了怪了，于是把另一個數(shù)組的類型從int改成Integer，結果就過了，不懂為什么了，（可能是引用類型的原因）下面是代碼：