CF1420A Cubes Sorting

拜托了，你们可是长着腿的箱子！你们唯一的用途就是这个！走到按钮上！你们怎么连自己被设计出来的唯一一件事都做不好？哦，这很好笑，是吗？很好笑？因为我们已经搞了十二个小时了，你也没解决，所以我不知道你为什么在笑。你还有一个小时！解决它！ Wheatley 决定尝试制作一个测试间。他做了一个很棒的测试间，但只有一个细节缺失——立方体。 为了完成测试间，Wheatley 需要 $n$ 个立方体。第 $i$ 个立方体的体积为 $a_i$。 Wheatley 必须将立方体按体积非递减顺序摆放。形式化地说，对于每个 $i>1$，都必须满足 $a_{i-1} \le a_i$。 为此，他可以交换任意两个相邻的立方体。也就是说，对于任意 $i>1$，你可以交换第 $i-1$ 个和第 $i$ 个立方体。 但问题是：Wheatley 非常没有耐心。如果需要超过 $\frac{n \cdot (n-1)}{2}-1$ 次交换操作，他就不会做这件无聊的事情。 Wheatley 想知道：在这样的条件下，能否将立方体排序？

每组测试数据包含多组测试用例。 第一行包含一个正整数 $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$。

对于每个测试用例，输出一行单词：“YES”（不带引号），如果可以在规定次数内将立方体排序，否则输出 “NO”。

在第一个测试用例中，可以通过 $7$ 次交换将所有立方体排序。 在第二个测试用例中，立方体已经排好序。 在第三个测试用例中，我们不能进行任何交换，但立方体还没有排好序，所以答案是 “NO”。 由 ChatGPT 4.1 翻译