该比赛已结束，您无法在比赛模式下提交该题目。您可以点击“在题库中打开”以普通模式查看和提交本题。

背景

小李在和宁次玩一个关于数组的小游戏，小李有点笨尽管他能作弊，他还不知道怎么赢，只好找你帮他判断他能不能赢了。

题目描述

给你一个包含 $n$ 个数的数组 $a$ ,小李和宁次会围绕这个数组共进行（n-1）轮游戏，当游戏结束后,如果对于数组里的 $1 \le i < n$都满足 $a_i \le a_{i+1}$，小李就赢了，否则宁次赢。 下面是游戏规则；

• 1.小李在所有奇数轮出手，宁次在所有偶数轮出手。

• 2.在本轮出手的人可以进行选择

  （1）交换$a_i$ 和 $a_{i+1}$.

  （2）不改变数组，直接跳到下一轮（如果第 $i$ 轮是最后一轮，则结束游戏）

• 3.小李有一个作弊手段，他可以提前任意排列数组。

根据游戏规则判断小李能否找到一个排列让自己获胜.

输入

每个测试包含多个测试用例。

第一行包含测试用例的数量 $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里的元素进行重新排序，从而保证他的策略获胜，则在单独一行中输出"YES"，否则输出"NO"。

样例

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

YES
YES
NO

对于第一个例子的解释 数组$a = [4, 2, 2, 1]$.小李会赢的一种排列方案是: >$a = [2, 1, 2, 4]$. 游戏会按照下面进行；

1. 在第$1$轮, 小李先走 ，他会交换$a_1$ ， $a_2$, 现在数组 $a = [1, 2, 2, 4]$.
2. 在第$2$轮,轮到宁次了，无论他是交换还是跳过，数组都不会改变，现在数组 $a = [1, 2, 2, 4]$.
3. 在第$3$轮, 到小李的回合了，因为现在的数组已经满足他获胜的条件了，所以小李直接跳过。

$n$-1 轮结束后, $a = [1, 2, 2, 4]$, 按照不递减的顺序排列，因此无论宁次如何走，小李都会获胜。

限制

1s, 1024KiB for each test case.