D. Построение дерева
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Васе задали по информатике сложную задачу. К сожалению, Вася не умеет программировать и не смог найти решение в Интернете. Поэтому он обратился за помощью к Вам.

У нас есть последовательность $$$a$$$ из $$$n$$$ различных чисел, с помощью которой строится бинарное дерево поиска. Опишем правила построения формально.

  1. Первое число $$$a_1$$$ становится корнем дерева.
  2. Последовательно добавляются все элементы $$$a_2, a_3, \ldots, a_n$$$. При добавлении элемента $$$a_i$$$ выполняется спуск по дереву от корня вниз, по следующим правилам:
    1. Изначально текущей вершиной является корень.
    2. Если значение $$$a_i$$$ больше значения в текущем элементе, то правый сын текущей вершины становится текущей вершиной. В противном случае текущей вершиной становится левый сын.
    3. В момент когда требуемый переход в сына невозможен (то есть такой сын отсутствует) создаётся новая вершина, в которую записывается число $$$a_i$$$. Эта вершина становится соответствующим сыном текущей вершины.
Входные данные

В первой строке входных данных записано целое число $$$n$$$ ($$$2 \leq n \leq 100\,000$$$) — количество элементов в последовательности $$$a$$$.

Во второй строке записаны $$$n$$$ различных целых чисел $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) — исходная последовательность $$$a$$$.

Выходные данные

Выведите $$$n - 1$$$ число. Для всех $$$i > 1$$$ выведите значение, записанное в вершине являющей предком вершины с числом $$$a_i$$$.

Примеры
Входные данные
3
1 2 3
Выходные данные
1 2
Входные данные
5
4 2 3 1 6
Выходные данные
4 2 2 4