У Moamen есть массив из \(n\) различных целых чисел. Он хочет отсортировать его в неубывающем порядке, проделав следующую операцию ровно один раз:
- Разделить массив на ровно \(k\) непустых подотрезка таких, что каждый элемент принадлежит ровно одному подотрезку.
- Переупорядочить эти подотрезки произвольным образом.
- Объединить подотрезки в один массив.
Последовательность \(a\) является подотрезком \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного или всех) элементов из начала и нескольких (возможно, ни одного или всех) элементов из конца.
Помогите Moamen понять, существует ли способ отсортировать массив в неубывающем порядке, применив эту операцию ровно один раз?
Выходные данные
Для каждого набора входных данных выведите одну строку.
Если Moamen может отсортировать массив в неубывающем порядке, выведите «YES» (без кавычек). В противном случае выведите «NO» (без кавычек).
Вы можете выводить каждую букву «YES» и «NO» в любом регистре (верхнем или нижнем).
Примечание
В первом наборе входных данных \(a = [6, 3, 4, 2, 1]\), и \(k = 4\). Мы можем применить операцию следующим образом:
- Разбить \(a\) на \(\{ [6], [3, 4], [2], [1] \}\).
- Переупорядочить их: \(\{ [1], [2], [3,4], [6] \}\).
- Объединить их: \([1, 2, 3, 4, 6]\), получив отсортированный массив.
Во втором примере не существует способа отсортировать массив, разбив его всего на два \(2\) подотрезка.
Например, если мы разобьем массив на подотрезки как \(\{ [1, -4], [0, -2] \}\), мы можем переупорядочить их только как \(\{ [1, -4], [0, -2] \}\) или \(\{ [0, -2], [1, -4] \}\). В обоих случаях массив не будет отсортирован после объединения.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5 4
6 3 4 2 1
4 2
1 -4 0 -2
5 1
1 2 3 4 5
|
Yes
No
Yes
|