← 返回题目列表

Codeforces · 2163/A

A. 烤肉串 VS。卡拉马基

中文机器翻译题面 查看原题

两名玩家,Souvlaki 和 Kalamaki,被赋予 $$$a$$$ 的 $$$n$$$ 整数序列。

他们将玩一场由 $$$n-1$$$ 轮组成的游戏,编号从 $$$1$$$ 到 $$$n-1$$$。 Souvlaki 在奇数轮比赛,Kalamaki 在偶数轮比赛。

在第 $$$i$$$ 轮中,玩家可以选择准确地采取 一 以下操作:

  • 跳过他的回合并继续进行 $$$i+1$$$ 轮(或者如果 $$$i$$$ 轮是最后一轮则结束游戏)。
  • 交换元素 $$$a_i$$$ 和 $$$a_{i+1}$$$。

如果在最后一轮结束后,$$$a$$$ 被排序为 Souvlaki 获胜 非递减 订单。换句话说,如果 $$$a_i \le a_{i+1}$$$ 对于每个 $$$1 \le i \lt n$$$ 成立,他就获胜。否则,卡拉马基获胜。

然而,Souvlaki 不喜欢失败,所以 之前 游戏开始时,他可以按照他想要的任何方式重新排序$$$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$$$ 个元素。

输出

对于每个测试用例,如果 Souvlaki 可以重新排序 $$$a$$$ 的元素以便他有保证的获胜策略,则在单独的行上输出“'YES”',否则输出“'NO”。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“'yEs”'、“'yes”'、“'Yes”'和“'YES”'将被识别为肯定响应。

示例

输入
复制

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

注意

在第一个示例中,$$$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]$$$,按非递减顺序排序,因此 Souvlaki 获胜,无论 Kalamaki 选择如何玩。

在第二个示例中,由于每个元素都相等,因此 Souvlaki 始终会获胜,因为 $$$a$$$ 始终按非降序排序。