题目描述

有两位玩家，Souvlaki 和 Kalamaki，得到了一个长度为 $n$ 的整数序列 $a$。

他们将玩一个包含 $n-1$ 轮的游戏，轮次编号从 $1$ 到 $n-1$。Souvlaki 在奇数轮出手，Kalamaki 在偶数轮出手。

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

• 跳过本回合，进入第 $i+1$ 轮（如果本轮已经是最后一轮，则游戏结束）。
• 交换 $a_i$ 和 $a_{i+1}$ 两个元素。

如果在最后一轮结束后，序列 $a$ 是非递减的（即对于每个 $1 \le i < n$，都有 $a_i \le a_{i+1}$），则 Souvlaki 获胜。否则，Kalamaki 获胜。

然而，Souvlaki 不喜欢输，所以在游戏开始之前，他可以任意重新排列 $a$ 中的元素。请判断他是否可以重新排列 $a$，使得无论 Kalamaki 如何操作，他都一定能获胜。

输入格式

每个测试点包含多组测试数据。第一行包含一个整数 $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$ 的每个元素。

输出格式

对于每组测试数据，若 Souvlaki 能通过重新排列 $a$ 来保证自己获胜，输出 “YES”，否则输出 “NO”。

输出不区分大小写，例如 “yEs”、“yes”、“Yes” 和 “YES” 均视为正确答案。

说明/提示

在第一个样例中，$a = [4, 2, 2, 1]$。可以将序列重新排列为 $a = [2, 1, 2, 4]$，此时 Souvlaki 可以这样获胜：

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]$，始终是非递减的，所以 Souvlaki 获胜，无论 Kalamaki 如何选择。

在第二个样例中，因为所有元素都相等，序列始终是非递减的，所以 Souvlaki 一定获胜。

由 ChatGPT 5 翻译

样例

5
4
4 2 2 1
4
1 1 1 1
5
1 5 1 5 1
3
1 2 3
5
1 3 2 3 5

YES
YES
YES
NO
NO