给定一个大小为 $n$ 的排列 $a$。你可以进行如下操作：

• 选择一个下标 $i$（$2 \le i \le n-1$），满足 $a_{i-1} < a_i$ 且 $a_i > a_{i+1}$；
• 交换 $a_i$ 与 $a_{i+1}$。

请判断：经过有限次操作后，是否可能将该排列排序为非递减序列（即变为 $[1,2,\dots,n]$）。

排列的定义

排列是一个长度为 $n$ 的数组，包含从 $1$ 到 $n$ 的 $n$ 个互不相同的整数，顺序任意。 例如，$[2,3,1,5,4]$ 是排列；但 $[1,2,2]$ 不是（$2$ 重复出现），$[1,3,4]$ 也不是（$n=3$ 却出现了 $4$）。

输入格式

输入包含多组测试用例。第一行一个整数 $t$（$1 \le t \le 5000$），表示测试用例数量。

每个测试用例：

• 第一行一个整数 $n$（$3 \le n \le 10$），表示排列大小；
• 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1 \le a_i \le n$），表示排列 $a$。

输出格式

对每个测试用例输出一行：

• 若可以通过若干次操作将排列排序，输出 YES；
• 否则输出 NO。

说明：原题允许任意大小写，但为适配固定判题平台，本题要求严格输出大写 YES 或 NO。

样例

输入

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

输出

YES
YES
NO
NO
NO
NO