Теофанис очень занят после предыдущего контеста, ведь теперь ему нужно доставлять халлуми по всему миру. Он сложил сыр в \(n\) коробок, на каждой из которых написано некоторое число \(a_i\).
Теофанис хочет отсортировать коробки по неубыванию чисел на коробках, но его машина работает странным образом. Она может только разворачивать подмассивы\(^{\dagger}\) ящиков длины не более \(k\).
Найдите, можно ли отсортировать ящики за любое число разворотов.
\(^{\dagger}\) Развернуть подмассив массива — значит выбрать два индекса \(i\) и \(j\) (где \(1 \le i \le j \le n\)) и изменить массив \(a_1, a_2, \ldots, a_n\) на \(a_1, a_2, \ldots, a_{i-1}, \; a_j, a_{j-1}, \ldots, a_i, \; a_{j+1}, \ldots, a_{n-1}, a_n\). Тогда длина подмассива равна \(j - i + 1\).
Выходные данные
Для каждого набора входных данных выведите YES (в любом регистре), если массив может быть отсортирован в неубывающем порядке, или NO (в любом регистре) в противном случае.
Примечание
В первых двух наборах входных данных коробки уже отсортированы в неубывающем порядке.
В третьем наборе входных данных мы можем развернуть весь массив.
В четвертом наборе входных данных мы можем развернуть первые два ящика и последние два ящика.
В пятом наборе входных данных можно показать, что отсортировать ящики невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 2
1 2 3
3 1
9 9 9
4 4
6 4 2 1
4 3
10 3 830 14
2 1
3 1
|
YES
YES
YES
YES
NO
|