Вам заданы три массива \(a\), \(b\) и \(c\). Первоначально, массив \(a\) состоит из \(n\) элементов, массивы \(b\) и \(c\) — пустые.
Вы выполняете над ними следующий алгоритм, состоящий из двух шагов:
- Шаг \(1\): пока \(a\) не пуст, вы забираете из \(a\) последний элемент и перемещаете его в середину массива \(b\). Если \(b\) в данный момент нечетной длины, то вы сами можете выбрать: вставить число из \(a\) слева или справа от центрального элемента в \(b\). В результате \(a\) станет пустым, а \(b\) будет состоять из \(n\) элементов.
- Шаг \(2\): пока \(b\) не пуст, вы забираете из \(b\) центральный элемент и перемещаете его в конец массива \(c\). Если \(b\) в данный момент четной длины, то вы сами можете выбрать какой из двух центральных элементов забрать. В результате \(b\) станет пустым, а \(c\) теперь состоит из \(n\) элементов.
Обратитесь к Примечанию за примерами.
Можете ли вы получить отсортированный в порядке неубывания массив \(c\)?
Выходные данные
Для каждого набора входных данных, выведите YES (регистр не важен), если вы можете получить отсортированный по неубыванию массив \(c\). В противном случае выведите NO (регистр не важен).
Примечание
В первом наборе входных данных, мы можем сделать следующие преобразования массива \(a = [3, 1, 5, 3]\):
Шаг \(1\):
| \(a\) | \([3, 1, 5, 3]\) | \(\Rightarrow\) | \([3, 1, 5]\) | \(\Rightarrow\) | \([3, 1]\) | \(\Rightarrow\) | \([3]\) | \(\Rightarrow\) | \([]\) |
| \(b\) | \([]\) | | \([\underline{3}]\) | | \([3, \underline{5}]\) | | \([3, \underline{1}, 5]\) | | \([3, \underline{3}, 1, 5]\) |
Шаг \(2\):
| \(b\) | \([3, 3, \underline{1}, 5]\) | \(\Rightarrow\) | \([3, \underline{3}, 5]\) | \(\Rightarrow\) | \([\underline{3}, 5]\) | \(\Rightarrow\) | \([\underline{5}]\) | \(\Rightarrow\) | \([]\) |
| \(c\) | \([]\) | | \([1]\) | | \([1, 3]\) | | \([1, 3, 3]\) | | \([1, 3, 3, 5]\) |
В результате массив
\(c = [1, 3, 3, 5]\) и он отсортирован.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4
3 1 5 3
3
3 2 1
1
7331
|
YES
NO
YES
|