← 返回题目列表

Codeforces · 1420/A

A. 立方体排序

中文机器翻译题面 查看原题

惠特利决定尝试制作一个测试室。他做了一个不错的测试室,但只有一个细节缺失——立方体。

为了完成房间,惠特利需要 $$$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$$$交换操作,他就不会做这种无聊的工作。

Wheatly想知道:在这种条件下立方体可以排序吗?

输入

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

第一行包含一个正整数$$$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”(不带引号)。

示例

输入 #1

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

输出 #1

YES
YES
NO

注意

在第一个测试用例中,可以对 $$$7$$$ 交换中的所有立方体进行排序。

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

在第三个测试用例中,我们可以进行 $$$0$$$ 交换,但立方体尚未排序,所以答案是“否”。