D. Backrooms Hill
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Among the people from the city GR, there is a legend about a hill that leads to the backstage. An array $$$b$$$ consisting of $$$m$$$ integers is called a hill if there exists an index $$$k$$$ ($$$1\le k\le m$$$) such that the following conditions hold:

  • The first $$$k$$$ elements are strictly increasing. Formally, for all $$$i$$$ ($$$1\le i\lt k$$$), $$$b_i\lt b_{i+1}$$$.
  • The last $$$m-k+1$$$ elements are strictly decreasing. Formally, for all $$$i$$$ ($$$k\le i\lt m$$$), $$$b_i\gt b_{i+1}$$$.

You are given an array $$$a$$$ consisting of $$$n$$$ distinct integers. You may perform the following operation any number of times:

  • Choose any index $$$i$$$ ($$$1\le i\le n-2$$$).
  • Swap $$$a_i$$$ and $$$a_{i+2}$$$ in the array.

Your task is to determine whether it is possible to turn array $$$a$$$ into a hill by performing the operation any number of times.

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 test case contains an integer $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — the length of array $$$a$$$.

The second line of each test case contains $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le n$$$).

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 it is possible to make array $$$a$$$ a hill. Otherwise, print "NO".

You may print each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as positive answers.

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

In the first test case, it is impossible to turn array $$$a$$$ into a hill.

In the second test case, array $$$a$$$ is already a hill.

In the third test case, you can perform the operations as follows:

  • Swap $$$a_1$$$ and $$$a_3$$$. After this operation, array $$$a$$$ becomes $$$[4, 3, 5, 6, 2, 1]$$$.
  • Swap $$$a_2$$$ and $$$a_4$$$. After this operation, array $$$a$$$ becomes $$$[4, 6, 5, 3, 2, 1]$$$.
And array $$$[4, 6, 5, 3, 2, 1]$$$ is a hill.