CF2191A.Array Coloring

You have $n$ cards arranged in a row. The $i$-th card has the integer $a_i$ written on it. All integers are distinct.

You must color each card either $\color{red}{\text{red}}$ or $\color{blue}{\text{blue}}$ such that the following conditions are satisfied:

• Any two adjacent cards in the row have different colors.
• If you rearrange the cards so that the numbers on them are in increasing order, any two adjacent cards in the new row must also have different colors.

Determine if such a coloring exists.

你有 $n$ 张卡片排成一行。第 $i$ 张卡片上写有一个整数 $a_i$。所有整数互不相同。

你需要将每张卡片染成 $\color{red}{\text{红色}}$ 或 $\color{blue}{\text{蓝色}}$，使得满足以下条件：

• 行中任意两张相邻的卡片颜色不同；
• 若将卡片按其上的数字升序重新排列，则新行中任意两张相邻的卡片颜色也必须不同。

判断是否存在满足上述条件的染色方案。

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

The first line of each test case contains a single integer $n$ ($2 \le n \le 100$) — the length of the array.

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

It is guaranteed that all elements of $a$ are distinct.

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

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 100$）—— 表示数组的长度。

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

保证数组 $a$ 中的所有元素互不相同。

For each test case, output "YES" if you can color the cards so that the conditions are satisfied, 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.

对于每个测试用例，如果可以对卡片进行染色以满足所有条件，则输出 “YES”，否则输出 “NO”。

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

In the first example, the cards are colored as $a = [\color{red}{2}, \color{blue}{3}, \color{red}{4}, \color{blue}{1}]$. After sorting, the cards become $[\color{blue}{1}, \color{red}{2}, \color{blue}{3}, \color{red}{4}]$. Both sequences satisfy the condition, so the answer is YES.

In the second example, no valid coloring exists. For instance, if we color the cards as $a = [\color{blue}{2}, \color{red}{3}, \color{blue}{1}]$, the sorted sequence becomes $[\color{blue}{1}, \color{blue}{2}, \color{red}{3}]$. Here, the adjacent elements $1$ and $2$ have the same color, so the condition is not satisfied.

In the third example, a possible coloring is $a = [\color{blue}{3}, \color{red}{4}, \color{blue}{1}, \color{red}{2}, \color{blue}{5}]$. After sorting, the cards become $[\color{blue}{1}, \color{red}{2}, \color{blue}{3}, \color{red}{4}, \color{blue}{5}]$.

在第一个例子中，卡片的颜色为 $a = [\color{red}{2}, \color{blue}{3}, \color{red}{4}, \color{blue}{1}]$。排序后，卡片变为 $[\color{blue}{1}, \color{red}{2}, \color{blue}{3}, \color{red}{4}]$。两个序列均满足条件，因此答案为 YES。

在第二个例子中，不存在合法的染色方案。例如，若将卡片染色为 $a = [\color{blue}{2}, \color{red}{3}, \color{blue}{1}]$，则排序后的序列为 $[\color{blue}{1}, \color{blue}{2}, \color{red}{3}]$。此时相邻元素 $1$ 和 $2$ 颜色相同，不满足条件。

在第三个例子中，一种可能的染色方案是 $a = [\color{blue}{3}, \color{red}{4}, \color{blue}{1}, \color{red}{2}, \color{blue}{5}]$。排序后，卡片变为 $[\color{blue}{1}, \color{red}{2}, \color{blue}{3}, \color{red}{4}, \color{blue}{5}]$。