Господи, вы же просто ящики с ногами! Это же ваше единственное назначение — жать на кнопки! Как можно не уметь то, для чего вы были созданы?О, как смешно! Мы тут уже двенадцать часов торчим, а вы всё еще не закончили. Не понимаю, чего это вам так весело. У вас один час! Решите задачу!
Уитли решил попробовать себя в создании тестовых камер. Он создал отличную камеру, но в ней не хватало лишь одной детали — кубов.
В камеру необходимо было доставить \(n\) кубов. \(i\)-й куб имеет объем \(a_i\).
Уитли необходимо расставить кубы так, чтобы они были отсортированы в порядке неубывания объема. Строго говоря, для каждого \(i>1\) должно выполняться условие \(a_{i-1} \le a_i\).
Для этого Уитли может менять местами две соседние кубы, то есть для любого \(i>1\) можно поменять местами кубы на позициях \(i-1\) и \(i\).
Проблема в том, что Уитли нетерпелив. Если ему придется сделать больше, чем \(\frac{n \cdot (n-1)}{2}-1\) операций обмена, он не захочет делать столь нудную работу.
Уитли надо узнать: можно ли расставить кубы в порядке неубывания обьема, соблюдая все условия?
Выходные данные
Для каждого набора входных данных выведите в отдельной строке одно слово: «YES» (без кавычек), если кубы могут быть отсортированы при заданных условиях, и «NO» (без кавычек) иначе.
Примечание
В первом наборе входных данных возможно отсортировать все кубы, используя \(7\) операций обмена.
Во втором наборе входных данных все кубы уже отсортированы.
В третьем наборе входных данных мы можем сделать \(0\) обменов, однако кубы еще не отсортированы, поэтому отсортировать мы их не можем.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5
5 3 2 1 4
6
2 2 2 2 2 2
2
2 1
|
YES
YES
NO
|