У вас есть массив \(a\) из \(n\) положительных чисел.
Вы можете выполнять следующую операцию:
- выберите два индекса \(l\) и \(r\) (\(1 \leq l \leq r \leq n\)), затем
- уменьшите элементы \(a_l, a_{l + 1}, \dots, a_r\) на \(1\) каждый.
Пусть \(f(a)\) равно минимальному числу операций, необходимому, чтобы превратить массив \(a\) в массив из \(n\) нулей.
Определите, верно ли, что для всех перестановок\(^\dagger\) \(b\) массива \(a\) выполняется \(f(a) \leq f(b)\).
\(^\dagger\) Массив \(b\) является перестановкой массива \(a\), если \(b\) состоит из элементов массива \(a\) в произвольном порядке. Например, \([4,2,3,4]\) является перестановкой \([3,2,4,4]\), а \([1,2,2]\) не является перестановкой \([1,2,3]\).
Выходные данные
Для каждого набора входных данных выведите «YES» (без кавычек), если для всех перестановок \(b\) массива \(a\) выполняется \(f(a) \leq f(b)\), и «NO» (без кавычек) иначе.
Вы можете выводить буквы в «YES» и «NO» в любом регистре (например, строки «yEs», «yes» и «Yes» будут приняты как положительный ответ).
Примечание
В первом примере можно превратить все элементы в \(0\) за \(5\) операций. Можно показать, что не существует перестановки массива \([2, 3, 5, 4]\) такой, что все ее элементы можно превратить в \(0\) меньше чем за \(5\).
В третьем примере необходимо \(5\) операций, чтобы превратить все элементы в \(0\), а перестановка, равная \([2, 3, 3, 1]\), требует только \(3\) операции.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4
2 3 5 4
3
1 2 3
4
3 1 3 2
|
YES
YES
NO
|