D. Reserved Reversals
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ consisting of $$$n$$$ positive integers.

For any segment of the array starting at position $$$l$$$ and ending at position $$$r$$$ ($$$1 \le l \le r \le n$$$), let $$$m(l, r)$$$ denote the minimum value in that segment, and $$$M(l, r)$$$ denote the maximum value in that segment. Formally,

$$$$$$ \begin{aligned} m(l,r) &= \min(a_l, a_{l+1}, \ldots, a_r),\\ M(l,r) &= \max(a_l, a_{l+1}, \ldots, a_r).\\ \end{aligned} $$$$$$

You may perform the following operation any number of times (possibly zero):

  • Select two indices $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) such that $$$m(l, r) + M(l, r)$$$ is odd;
  • Reverse the entire segment $$$a_l, a_{l+1}, \ldots, a_r$$$. In other words, for every $$$i$$$ with $$$l \le i \le r$$$, set $$$a_i := a_{l+r-i}$$$ simultaneously.

Determine whether you can make the array $$$a$$$ non-decreasing$$$^{\text{∗}}$$$ by performing a series of operations.

$$$^{\text{∗}}$$$An array $$$[b_1, b_2, \ldots, b_k]$$$ is considered non-decreasing iff $$$b_1 \le b_2 \le \ldots \le b_k$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — the length of the array $$$a$$$.

The second line of each testcase contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output

For each test case, print "YES" if you can make the array $$$a$$$ non-decreasing, and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Example
Input
6
4
1 1 2 3
3
2 1 3
5
5 4 3 2 1
6
4 1 2 3 3 6
5
4 2 4 2 4
6
3 3 1 5 5 2
Output
YES
YES
NO
YES
NO
NO
Note

For the first testcase, the array is already non-decreasing. Hence, output YES.

For the second testcase, let us choose $$$l = 1$$$ and $$$r = 2$$$. We can see that $$$\min(2, 1) + \max(2, 1) = 2 + 1 = 3$$$, which is odd. Thus, after simultaneously assigning $$$a_i := a_{3-i}$$$ for all $$$1 \le i \le 2$$$, we get $$$a = [1, 2, 3]$$$, which is non-decreasing.

Consider the fourth testcase,

  • Operation 1: Choose $$$l = 1$$$, $$$r = 3$$$. The array becomes $$$a = [2, 1, 4, 3, 3, 6]$$$.
  • Operation 2: Choose $$$l = 3$$$, $$$r = 5$$$. The array becomes $$$a = [2, 1, 3, 3, 4, 6]$$$.
  • Operation 3: Choose $$$l = 1$$$, $$$r = 2$$$. The array becomes $$$a = [1, 2, 3, 3, 4, 6]$$$.

For the fifth testcase, note that it is impossible to choose indices $$$l$$$ and $$$r$$$ satisfying the conditions. Hence, output NO.