Мальчик Женя захотел посадить в саду яблоню. Однако его жизнь была достаточно необычной, поэтому в своём возрасте из всех деревьев он знал только двоичные деревья поиска.

Двоичное дерево — это корневое дерево, в котором у каждой вершины есть не более двух сыновей (их называют левым и правым сыном).

Двоичное дерево поиска — это двоичное дерево, в каждой вершине которого записано число $$$k$$$, называемое ключом вершины, при этом верно следующее свойство:

1. Для любой вершины $$$u$$$ из поддерева левого сына $$$v$$$ выполняется $$$k_u$$$ < $$$k_v$$$;
2. Для любой вершины $$$u$$$ из поддерева правого сына $$$v$$$ выполняется $$$k_v$$$ < $$$k_u$$$.

Женя придумал двоичное дерево поиска, ключами в котором является перестановка размера $$$n$$$. Однако сегодняшний вечер у Жени уже был занят: он планировал встретиться с друзьями в небезызвестном ресторане «Брёвна». Поэтому, чтобы не забыть дерево, Женя решил записать информацию о нём на листочек. Рисовать он не умел, поэтому придумал специальный метод шифрования, чтобы гарантированно вспомнить дерево после встречи с друзьями:

[language=Python]
def encode_tree(v):
  if v is None:
    return []
  return [v.x] + encode_tree(v.left) + encode_tree(v.right)

Для приведённого дерева результат функции encode_tree будет $$$[4, 2, 1, 3, 5]$$$.

Однако Женя перехитрил сам себя: вернувшись домой вечером, он понял, что никак не может расшифровать написанные на листочке числа. Создание яблоневого сада под угрозой, поэтому вам требуется помочь Жене по заданной зашифрованной записи восстановить исходное дерево, либо же сообщить, что Женя что-то напутал, и по зашифрованной записи восстановить дерево невозможно.