Хемосе вместе со своими друзьями Самезом, Ахмедом, Ашрафом, Саваном и О_Е ходил по магазинам в Германии. Как вы знаете, Хемосе и его друзья решают задачи, поэтому они очень умны. Поэтому они отправятся во все магазины со скидками в Германии.
У Хемосе есть массив из \(n\) целых чисел. Он хочет, чтобы Самез отсортировал массив в неубывающем порядке. Поскольку для Самеза это было бы слишком простой задачей, Хемосе разрешает Самезу использовать только следующую операцию:
Выберите индексы \(i\) и \(j\) такие, что \(1 \le i, j \le n\), и \(\lvert i - j \rvert \geq x\). Затем поменяйте местами элементы \(a_i\) и \(a_j\).
Подскажите, пожалуйста, существует ли способ отсортировать массив в неубывающем порядке, используя вышеописанную операцию некоторое конечное число раз (возможно, \(0\))?
Выходные данные
Для каждого набора входных данных необходимо вывести одну строку.
Если Самез может отсортировать массив в неубывающем порядке с помощью операции, описанной выше, выведите «YES» (без кавычек). В противном случае выведите «NO» (без кавычек).
Вы можете вывести каждую букву «YES» и «NO» в любом регистре (верхнем или нижнем).
Примечание
В первом наборов входных данных вы не можете выполнить никаких операций.
Во втором наборе входных данных массив уже отсортирован.
В третьем наборе входных данных вы можете выполнить следующие операции:
- \([5,1,2,3,4]\), \(swap(a_1,a_3)\)
- \([2,1,5,3,4]\), \(swap(a_2,a_5)\)
- \([2,4,5,3,1]\), \(swap(a_2,a_4)\)
- \([2,3,5,4,1]\), \(swap(a_1,a_5)\)
- \([1,3,5,4,2]\), \(swap(a_2,a_5)\)
- \([1,2,5,4,3]\), \(swap(a_3,a_5)\)
- \([1,2,3,4,5]\)
(Здесь под \(swap(a_i, a_j)\) имеется в виду обмен местами элементов на позициях \(i\), \(j\)).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 3
3 2 1
4 3
1 2 3 4
5 2
5 1 2 3 4
5 4
1 2 3 4 4
|
NO
YES
YES
YES
|