CF2267D.Backrooms Hill

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.

在格鲁吉亚（GR）市的居民中，流传着一个关于通往后台的山丘的传说。由 $m$ 个整数组成的数组 $b$ 被称为山丘（hill），当且仅当存在某个下标 $k$（$1\le k\le m$），使得以下条件成立：

• 前 $k$ 个元素严格递增：即对所有 $i$（$1\le i\lt k$），有 $b_i\lt b_{i+1}$；
• 后 $m-k+1$ 个元素严格递减：即对所有 $i$（$k\le i\lt m$），有 $b_i\gt b_{i+1}$。

现给定一个由 $n$ 个互不相同的整数组成的数组 $a$。你可以执行以下操作任意多次：

• 任选一个下标 $i$（$1\le i\le n-2$）；
• 交换数组中位置 $i$ 和 $i+2$ 上的元素（即交换 $a_i$ 与 $a_{i+2}$）。

你的任务是判断：是否可以通过若干次上述操作，将数组 $a$ 变为一个山丘。

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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1\le n\le 2\cdot 10^5$）—— 数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个互不相同的整数 $a_1, a_2, \ldots, a_n$（$1\le a_i\le n$）。

保证所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$。

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.

对于每个测试用例，如果可以将数组 $a$ 变为一座“山”，则输出 "YES"；否则输出 "NO"。

你可以以任意大小写形式输出每个字母（小写或大写）。例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 均被视为有效的肯定回答。

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.

在第一个测试用例中，无法将数组 $a$ 变为山形数组。

在第二个测试用例中，数组 $a$ 已经是山形数组。

在第三个测试用例中，你可以执行如下操作：

• 交换 $a_1$ 和 $a_3$。该操作后，数组 $a$ 变为 $[4, 3, 5, 6, 2, 1]$。
• 交换 $a_2$ 和 $a_4$。该操作后，数组 $a$ 变为 $[4, 6, 5, 3, 2, 1]$。

而数组 $[4, 6, 5, 3, 2, 1]$ 是一个山形数组。