CF1420A.Cubes Sorting

For god's sake, you're boxes with legs! It is literally your only purpose! Walking onto buttons! How can you not do the one thing you were designed for?

Oh, that's funny, is it? Oh it's funny? Because we've been at this for twelve hours and you haven't solved it either, so I don't know why you're laughing. You've got one hour! Solve it!

Wheatley decided to try to make a test chamber. He made a nice test chamber, but there was only one detail absent — cubes.

For completing the chamber Wheatley needs $n$ cubes. $i$-th cube has a volume $a_i$.

Wheatley has to place cubes in such a way that they would be sorted in a non-decreasing order by their volume. Formally, for each $i \gt 1$, $a_{i-1} \le a_i$ must hold.

To achieve his goal, Wheatley can exchange two neighbouring cubes. It means that for any $i \gt 1$ you can exchange cubes on positions $i-1$ and $i$.

But there is a problem: Wheatley is very impatient. If Wheatley needs more than $\frac{n \cdot (n-1)}{2}-1$ exchange operations, he won't do this boring work.

Wheatly wants to know: can cubes be sorted under this conditions?

看在上帝的份上，你们就是长了腿的箱子！这 literally 就是你们存在的唯一目的！踩按钮！你们怎么连自己被设计出来的唯一任务都完不成？

哦，这很好笑，是吗？哦，很好笑？我们已经折腾了十二个小时，而你也没解出来，所以我不知道你到底在笑什么。你只剩一小时了！快解出来！

Wheatley 决定尝试建造一个测试室。他建好了一个不错的测试室，但唯独缺了一样东西——方块。

为了完成这个测试室，Wheatley 需要 $n$ 个方块。其中第 $i$ 个方块的体积为 $a_i$。

Wheatley 必须将这些方块按体积非递减顺序排列。形式化地说，对每个 $i > 1$，必须满足 $a_{i-1} \le a_i$。

为达成目标，Wheatley 可以交换两个相邻的方块。也就是说，对任意 $i > 1$，你可以交换位于位置 $i-1$ 和 $i$ 上的方块。

但这里有个问题：Wheatley 性子非常急。如果 Wheatley 需要执行超过 $\frac{n \cdot (n-1)}{2}-1$ 次交换操作，他就拒绝干这种无聊的活。

Wheatley 想知道：在上述条件下，这些方块能否被成功排序？

Each test contains multiple test cases.

The first line contains one positive integer $t$ ($1 \le t \le 1000$), denoting the number of test cases. Description of the test cases follows.

The first line of each test case contains one positive integer $n$ ($2 \le n \le 5 \cdot 10^4$) — number of cubes.

The second line contains $n$ positive integers $a_i$ ($1 \le a_i \le 10^9$) — volumes of cubes.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

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

第一行包含一个正整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个正整数 $n$（$2 \le n \le 5 \cdot 10^4$）—— 表示立方体的数量。

第二行包含 $n$ 个正整数 $a_i$（$1 \le a_i \le 10^9$）—— 表示各立方体的体积。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

For each test case, print a word in a single line: "YES" (without quotation marks) if the cubes can be sorted and "NO" (without quotation marks) otherwise.

对于每个测试用例，在一行中输出一个单词：“YES”（不带引号），如果方块可以被排序；否则输出“NO”（不带引号）。

In the first test case it is possible to sort all the cubes in $7$ exchanges.

In the second test case the cubes are already sorted.

In the third test case we can make $0$ exchanges, but the cubes are not sorted yet, so the answer is "NO".

在第一个测试用例中，可以通过 $7$ 次交换将所有立方体排序。

在第二个测试用例中，立方体已经排好序。

在第三个测试用例中，我们可以进行 $0$ 次交换，但此时立方体仍未排序，因此答案为 "NO"。