两名玩家,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”'将被识别为肯定响应。
示例
输入复制
544 2 2 141 1 1 151 5 1 5 131 2 351 3 2 3 5
输出复制
YESYESYESNONO
注意
在第一个示例中,$$$a = [4, 2, 2, 1]$$$。重新排序元素以便 Souvlaki 获胜的一种可能方法如下:$$$a = [2, 1, 2, 4]$$$。那么,游戏可能会这样进行:
- 在$$$1$$$轮上,轮到Souvlaki了。他会选择将 $$$a_1$$$ 与 $$$a_2$$$ 交换,现在 $$$a = [1, 2, 2, 4]$$$。
- 在$$$2$$$ 轮中,轮到Kalamaki 了。无论他选择跳过回合还是交换元素 $$$a_2$$$ 和 $$$a_3$$$,$$$a$$$ 将保持不变。假设他跳过了他的回合。
- 在$$$3$$$轮上,轮到Souvlaki了。他也可以选择跳过他的回合,因为如果他交换最后两个元素,他就会输掉。
每轮结束后,$$$a = [1, 2, 2, 4]$$$,按非递减顺序排序,因此 Souvlaki 获胜,无论 Kalamaki 选择如何玩。
在第二个示例中,由于每个元素都相等,因此 Souvlaki 始终会获胜,因为 $$$a$$$ 始终按非降序排序。