A. Сортировка кубов
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Господи, вы же просто ящики с ногами! Это же ваше единственное назначение — жать на кнопки! Как можно не уметь то, для чего вы были созданы?

О, как смешно! Мы тут уже двенадцать часов торчим, а вы всё еще не закончили. Не понимаю, чего это вам так весело. У вас один час! Решите задачу!

Уитли решил попробовать себя в создании тестовых камер. Он создал отличную камеру, но в ней не хватало лишь одной детали — кубов.

В камеру необходимо было доставить $$$n$$$ кубов. $$$i$$$-й куб имеет объем $$$a_i$$$.

Уитли необходимо расставить кубы так, чтобы они были отсортированы в порядке неубывания объема. Строго говоря, для каждого $$$i>1$$$ должно выполняться условие $$$a_{i-1} \le a_i$$$.

Для этого Уитли может менять местами две соседние кубы, то есть для любого $$$i>1$$$ можно поменять местами кубы на позициях $$$i-1$$$ и $$$i$$$.

Проблема в том, что Уитли нетерпелив. Если ему придется сделать больше, чем $$$\frac{n \cdot (n-1)}{2}-1$$$ операций обмена, он не захочет делать столь нудную работу.

Уитли надо узнать: можно ли расставить кубы в порядке неубывания обьема, соблюдая все условия?

Входные данные

Каждый тест содержит несколько наборов входных данных.

В первой строке находится одно целое положительное число $$$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» (без кавычек) иначе.

Пример
Входные данные
3
5
5 3 2 1 4
6
2 2 2 2 2 2
2
2 1
Выходные данные
YES
YES
NO
Примечание

В первом наборе входных данных возможно отсортировать все кубы, используя $$$7$$$ операций обмена.

Во втором наборе входных данных все кубы уже отсортированы.

В третьем наборе входных данных мы можем сделать $$$0$$$ обменов, однако кубы еще не отсортированы, поэтому отсортировать мы их не можем.