Вам дана перестановка\(^\dagger\) \(a\) длины \(n\). Вы можете применять следующую операцию:
- Выбрать индекс \(i\) от \(2\) до \(n - 1\) такой, что \(a_{i - 1} < a_i\) и \(a_i > a_{i+1}\), и поменять местами \(a_i\) и \(a_{i+1}\).
Определите, можно ли отсортировать перестановку, применив конечное число операций.
\(^\dagger\) Перестановкой является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Выходные данные
Для каждого набора входных данных выведите «YES», если перестановку можно отсортировать, и «NO» в противном случае.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
Примечание
В первом наборе входных данных перестановка уже отсортирована.
Во втором наборе входных данных мы можем выбрать индекс \(i=2\), так как \(1<3\) и \(3>2\), и получить массив \([1, 2, 3, 5, 4]\). Затем можно выбрать индекс \(i=4\), так как \(3<5\) и \(5>4\), и получить \([1, 2, 3, 4, 5]\).
В третьем наборе входных данных можно доказать, что отсортировать перестановку невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3
1 2 3
5
1 3 2 5 4
5
5 4 3 2 1
3
3 1 2
4
2 3 1 4
5
5 1 2 3 4
|
YES
YES
NO
NO
NO
NO
|