CF2226D.Reserved Reversals

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

给你一个由 $n$ 个正整数组成的数组 $a$。

对于数组中任意一个起始于位置 $l$、终止于位置 $r$ 的子段（其中 $1 \le l \le r \le n$），记 $m(l, r)$ 为该子段中的最小值，$M(l, r)$ 为该子段中的最大值。形式化地，

$$\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}$$

你可以执行以下操作任意多次（包括零次）：

• 选择两个下标 $l$ 和 $r$（满足 $1 \le l \le r \le n$），使得 $m(l, r) + M(l, r)$ 为奇数；
• 将整个子段 $a_l, a_{l+1}, \ldots, a_r$ 翻转。换言之，对每个满足 $l \le i \le r$ 的 $i$，同时令 $a_i := a_{l+r-i}$。

判断是否可以通过一系列上述操作，使数组 $a$ 变为非递减序列$^{\text{∗}}$。

$^{\text{∗}}$ 数组 $[b_1, b_2, \ldots, b_k]$ 被称为非递减的，当且仅当 $b_1 \le b_2 \le \ldots \le b_k$。

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

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

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

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）—— 数组的元素。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot10^5$。

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.

对于每个测试用例，如果可以使数组 $a$ 变为非递减的，则输出 "YES"；否则输出 "NO"。

你可以以任意大小写形式输出答案（大写或小写均可）。例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 均会被识别为肯定回答。

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.

对于第一个测试用例，数组已经是非递减的，因此输出 YES。

对于第二个测试用例，我们选择 $l = 1$ 和 $r = 2$。可以验证 $\min(2, 1) + \max(2, 1) = 2 + 1 = 3$，该值为奇数。因此，在对所有 $1 \le i \le 2$ 同时执行赋值操作 $a_i := a_{3-i}$ 后，得到 $a = [1, 2, 3]$，该数组是非递减的。

考虑第四个测试用例：

• 操作 1：选择 $l = 1$，$r = 3$，数组变为 $a = [2, 1, 4, 3, 3, 6]$。
• 操作 2：选择 $l = 3$，$r = 5$，数组变为 $a = [2, 1, 3, 3, 4, 6]$。
• 操作 3：选择 $l = 1$，$r = 2$，数组变为 $a = [1, 2, 3, 3, 4, 6]$。

对于第五个测试用例，注意不存在满足条件的下标 $l$ 和 $r$。因此输出 NO。