CF2163A.Souvlaki VS. Kalamaki

Two players, Souvlaki and Kalamaki, are given a sequence $a$ of $n$ integers.

They will play a game that consists of $n-1$ rounds, which are numbered from $1$ to $n-1$. Souvlaki plays on odd-numbered rounds, and Kalamaki on even-numbered rounds.

On the $i$-th round, a player can choose to take exactly one of the following actions:

• Skip his turn and proceed to round $i+1$ (or finish the game if round $i$ was the last one).
• Swap elements $a_i$ and $a_{i+1}$.

Souvlaki wins if after the end of the last round, $a$ is sorted in non-decreasing order. In other words, he wins if $a_i \le a_{i+1}$ holds for every $1 \le i \lt n$. Otherwise, Kalamaki wins.

However, Souvlaki does not like losing, so before the start of the game, he may re-order the elements of $a$ in anyway he wants. Is it possible for him to do so such that he has a guaranteed winning strategy?

两名玩家 Souvlaki 和 Kalamaki 被给定一个由 $n$ 个整数组成的序列 $a$。

他们将进行一场包含 $n-1$ 轮的游戏，轮次编号为 $1$ 至 $n-1$。Souvlaki 在奇数轮行动，Kalamaki 在偶数轮行动。

在第 $i$ 轮中，当前玩家可选择执行以下操作之一：

• 跳过本轮，直接进入第 $i+1$ 轮（若第 $i$ 轮已是最后一轮，则游戏结束）；
• 交换元素 $a_i$ 与 $a_{i+1}$。

若游戏结束后序列 $a$ 按非递减顺序排列，则 Souvlaki 获胜。即：对所有满足 $1 \le i < n$ 的 $i$，均有 $a_i \le a_{i+1}$。否则，Kalamaki 获胜。

然而，Souvlaki 不喜欢输掉游戏，因此在游戏开始前，他可以以任意方式重新排列序列 $a$ 中的元素。问：是否存在一种重排方式，使得 Souvlaki 拥有必胜策略？

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

The first line of each test case contains a single integer, $n$ ($3 \le n \le 100$) — the number of integers in $a$.

The second line contains exactly $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — where $a_i$ represents the $i$-th element of $a$.

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

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

第二行包含恰好 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）——其中 $a_i$ 表示数组 $a$ 的第 $i$ 个元素。

For each test case, output on a separate line "'YES"' if it is possible for Souvlaki to re-order the elements of $a$ such that he has a guaranteed winning strategy, 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.

对于每个测试用例，如果 Souvlaki 能够重新排列数组 $a$ 的元素，从而确保自己拥有必胜策略，则在单独一行输出 "YES”；否则输出 "NO”。

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

In the first example, $a = [4, 2, 2, 1]$. A possible way to re-order the elements so that Souvlaki can win is the following: $a = [2, 1, 2, 4]$. Then, the game might go as follows:

1. On round $1$, it is Souvlaki's turn. He will choose to swap $a_1$ with $a_2$, and now $a = [1, 2, 2, 4]$.
2. On round $2$, it is Kalamaki's turn. Whether he chooses to skip his turn or swap elements $a_2$ and $a_3$, $a$ will remain the same. Suppose he skips his turn.
3. On round $3$, it is Souvlaki's turn. He can choose to skip his turn as well, because if he swapped the last two elements he would lose.

After every round, $a = [1, 2, 2, 4]$, sorted in non-decreasing order, so Souvlaki wins, no matter how Kalamaki chooses to play.

On the second example, since every element is equal, Souvlaki will always win because $a$ is always sorted in non-decreasing order.

在第一个例子中，$a = [4, 2, 2, 1]$。一种能使 Souvlaki 获胜的重排元素的方式如下：$a = [2, 1, 2, 4]$。此时，游戏可能按如下方式进行：

1. 第 $1$ 轮，轮到 Souvlaki 行动。他选择交换 $a_1$ 与 $a_2$，于是 $a = [1, 2, 2, 4]$。
2. 第 $2$ 轮，轮到 Kalamaki 行动。无论他选择跳过本轮，还是选择交换 $a_2$ 与 $a_3$，数组 $a$ 均保持不变。假设他选择跳过本轮。
3. 第 $3$ 轮，轮到 Souvlaki 行动。他也可以选择跳过本轮，因为若他交换最后两个元素，则将输掉游戏。

每轮结束后，$a = [1, 2, 2, 4]$ 均为非递减序排列，因此无论 Kalamaki 如何行动，Souvlaki 均获胜。

在第二个例子中，由于所有元素均相等，$a$ 始终处于非递减序排列，因此 Souvlaki 总是获胜。