Вам дана перестановка \(a_1, a_2, \ldots, a_n\) размера \(n\), где каждое целое число от \(1\) до \(n\) встречается ровно один раз.
Вы можете выполнить следующую операцию любое количество раз (возможно, ноль):
- Выбрать любые три индекса \(i, j, k\) (\(1 \le i < j < k \le n\)).
- Если \(a_i > a_k\), заменить \(a_i\) на \(a_i + a_j\). В противном случае поменять местами \(a_j\) и \(a_k\).
Определите, можно ли отсортировать массив \(a\) в порядке неубывания.
Выходные данные
Для каждого набора входных данных выведите «Yes» (без кавычек), если массив можно отсортировать в неубывающем порядке, и «No» (без кавычек) в противном случае.
Вы можете вывести «Yes» и «No» в любом регистре (например, строки «YES», «yEs» и «yes» будут распознаны как положительный ответ).
Примечание
В первом наборе входных данных массив \([1,2,3]\) уже отсортирован в порядке неубывания.
Во втором наборе входных данных мы можем выбрать \(i = 1,j = 2,k = 3\). Так как \(a_1 \le a_3\), поменяем местами \(a_2\) и \(a_3\), тогда массив станет \([1,2,3]\), который отсортирован в порядке неубывания.
В седьмом наборе входных данных мы можем последовательно выполнять следующие операции:
- Выберем \(i = 5,j = 6,k = 7\). Поскольку \(a_5 \le a_7\), поменяем местами \(a_6\) и \(a_7\), тогда массив станет \([1,2,6,7,4,5,3]\).
- Выберем \(i = 5,j = 6,k = 7\). Поскольку \(a_5 > a_7\), заменим \(a_5\) на \(a_5+a_6=9\), тогда массив станет \([1,2,6,7,9,5,3]\).
- Выберем \(i = 2,j = 5,k = 7\). Поскольку \(a_2 \le a_7\), поменяем местами \(a_5\) и \(a_7\), тогда массив станет \([1,2,6,7,3,5,9]\).
- Выберем \(i = 2,j = 4,k = 6\). Поскольку \(a_2 \le a_6\), поменяем местами \(a_4\) и \(a_6\), тогда массив станет \([1,2,6,5,3,7,9]\).
- Выберем \(i = 1,j = 3,k = 5\). Поскольку \(a_1 \le a_5\), поменяем местами \(a_3\) и \(a_5\), тогда массив станет \([1,2,3,5,6,7,9]\), который отсортирован в порядке неубывания.
В третьем, четвертом, пятом и шестом наборах входных данных можно показать, что массив нельзя отсортировать в порядке неубывания.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
3
1 2 3
3
1 3 2
7
5 3 4 7 6 2 1
7
7 6 5 4 3 2 1
5
2 1 4 5 3
5
2 1 3 4 5
7
1 2 6 7 4 3 5
|
Yes
Yes
No
No
No
No
Yes
|