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.
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$$$.
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.
441 6 3 233 1 214252 4 6 8 10
NONOYESYES
34-3 2 -1 41-10000000004-5 -7 0 2
YESYESNO
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.