Васе задали по информатике сложную задачу. К сожалению, Вася не умеет программировать и не смог найти решение в Интернете. Поэтому он обратился за помощью к Вам.
У нас есть последовательность \(a\) из \(n\) различных чисел, с помощью которой строится бинарное дерево поиска. Опишем правила построения формально.
- Первое число \(a_1\) становится корнем дерева.
- Последовательно добавляются все элементы \(a_2, a_3, \ldots, a_n\). При добавлении элемента \(a_i\) выполняется спуск по дереву от корня вниз, по следующим правилам:
- Изначально текущей вершиной является корень.
- Если значение \(a_i\) больше значения в текущем элементе, то правый сын текущей вершины становится текущей вершиной. В противном случае текущей вершиной становится левый сын.
- В момент когда требуемый переход в сына невозможен (то есть такой сын отсутствует) создаётся новая вершина, в которую записывается число \(a_i\). Эта вершина становится соответствующим сыном текущей вершины.
Выходные данные
Выведите \(n - 1\) число. Для всех \(i > 1\) выведите значение, записанное в вершине являющей предком вершины с числом \(a_i\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2 3
|
1 2
|
|
2
|
5
4 2 3 1 6
|
4 2 2 4
|