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

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

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