Пенчик и его друг Кохане путешествуют по Индонезии, и следующая их остановка — Сурабая!
В шумных продуктовых лавках Сурабайи Коханэ купил \(n\) палочек для сатэ и выложил их в линию, причем \(i\)-я палочка для сатэ имеет длину \(p_i\). Известно, что \(p\) — перестановка\(^{\text{∗}}\) длины \(n\).
Пенчик хочет отсортировать палочки для сатэ в порядке возрастания их длины, так, чтобы выполнялось \(p_i=i\) для всех \(1\le i\le n\). Для развлечения они придумали правило: они могут менять местами только соседние палочки для сатэ, длина которых отличается ровно на \(1\). Формально, они могут выполнить следующую операцию любое количество раз (возможно, ноль):
- Выбрать индекс \(i\) (\(1\le i\le n-1\)) такой, что \(|p_{i+1}-p_i|=1\);
- Поменять местами \(p_i\) и \(p_{i+1}\).
Определите, можно ли отсортировать перестановку \(p\), а значит и палочки для сатэ, выполнив вышеописанную операцию некоторое количество раз.
Выходные данные
Для каждого набора входных данных выведите «YES», если можно отсортировать перестановку \(p\) с помощью данных операций. В противном случае выведите «NO».
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
Примечание
В первом наборе входных данных мы можем отсортировать перестановку \(p = [2, 1, 3, 4]\), выполнив операцию над индексом \(1\) (\(|p_2 - p_1| = |1 - 2| = 1\)), в результате чего получим \(p = [1, 2, 3, 4]\).
Для второго набора входных данных можно доказать, что перестановку \(p = [4, 2, 3, 1]\) невозможно отсортировать данными операциями. Для примера приведём последовательности операций, которые можно выполнить над перестановкой:
- Выбрать \(i = 2\) (\(|p_3 - p_2| = |3 - 2| = 1\)). В результате получится \(p = [4, 3, 2, 1]\).
- Выбрать \(i = 1\) (\(|p_2 - p_1| = |3 - 4| = 1\)). В результате получится \(p = [3, 4, 2, 1]\).
- Выбрать \(i = 3\) (\(|p_4 - p_3| = |1 - 2| = 1\)). В результате получится \(p = [3, 4, 1, 2]\).
К сожалению, после выполнения этих операций перестановка \(p\) останется неотсортированной.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4
2 1 3 4
4
4 2 3 1
|
YES
NO
|