J. Triple Reverse Sort
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a permutation $$$a$$$ of length $$$n$$$.

On this permutation, we can perform the following operation multiple times:

  1. Select an index $$$i$$$ such that $$$1 \le i \le n-2$$$;
  2. Reverse the subarray $$$[a_i,a_{i+1},a_{i+2}]$$$.

Is it possible to sort the permutation?

A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input

Each test contains multiple testcases. The first line of each testcase contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of each testcase contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of permutation $$$a$$$.

The second line of each testcase contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$, all $$$a_i$$$ are pairwise distinct) — the elements of permutation $$$a$$$.

It is guaranteed that the sum of $$$n$$$ across all testcases does not exceed $$$2 \cdot 10^5$$$.

Output

For each testcase, print "YES" if $$$a$$$ can be sorted, or "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
1
1
2
2 1
3
3 2 1
4
4 3 2 1
5
1 3 2 5 4
5
3 4 5 2 1
Output
YES
NO
YES
NO
NO
YES
Note

In the first two testcases, no operations can be performed since $$$n \lt 3$$$. $$$[1]$$$ is already sorted, while $$$[2,1]$$$ is not.

In the third testcase, the permutation can be sorted by choosing $$$i=1$$$ and reversing $$$[a_1,a_2,a_3]$$$.

In the fourth and fifth testcases, it can be proven that $$$a$$$ cannot be sorted.