E. Magical Array
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Svetozar is also a programmer, but he writes code in magical programming languages.

Today his program contains an array $$$a$$$ of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$. Svetozar wants to sort it in non-decreasing order, that is, make each next element not less than the previous one.

The magic of the programming language is not yet under Svetozar's control, so he can only perform operations of the following kind: swap two adjacent elements $$$a_i$$$ and $$$a_{i+1}$$$, but only if their sum is odd. This operation may be applied any number of times (including zero). If Svetozar tries to swap other pairs of numbers, he will not succeed.

Determine whether Svetozar can make the array non-decreasing, or whether his abilities are not enough for that.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$): the number of test cases. Then, $$$t$$$ test cases follow.

The first line of a test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$): the length of the array.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ ($$$-10^9 \leq a_i \leq 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$$$.

Output

For each test case, print YES if the array can be made non-decreasing, and NO otherwise, on a separate line. You may print the words in any case.

Examples
Input
4
4
1 6 3 2
3
3 1 2
1
42
5
2 4 6 8 10
Output
NO
NO
YES
YES
Input
3
4
-3 2 -1 4
1
-1000000000
4
-5 -7 0 2
Output
YES
YES
NO
Note

Consider the second sample. In the first test case, it is enough to swap the two adjacent numbers $$$2$$$ and $$$-1$$$ to make the array non-decreasing. In the second test case, the array is already non-decreasing, so nothing needs to be swapped. In the third test case, it can be shown that it is impossible to make the array non-decreasing by swapping adjacent numbers while following the rules.