#include <iostream>
#include <cassert>
template< class T>
struct isBigger
{
//дефолтное сравнение
    bool  operator() (const T& rightElement, const T& leftElement) const
    {
        return rightElement > leftElement;
    }
};

template< class T>
bool isbigger(const T& leftElement, const T& rightElement)
{
    return leftElement > rightElement;
}


template <typename T>
class dequeue
{

    int last_index;// "голова" дека
    int first_index;//хвост дека
    int size;//размер массива, выделенного под наш дек
    int current_size;//текущий размер дека
    T* buffer;//массив в динамической памяти, для хранения дека
    void increase_size();

public:
    int get_size();
    void push_front(T element);
    void push_back(T element);
    T show();
    //Если нам надо положить элемент, нам ничего не надо возвращать
    T pop_back();
    T pop_front();
    //Если хотим достать, нам не нужны аргументы
    //Запретим копирование
    dequeue( const dequeue& ) = delete;
    void operator=( const dequeue& ) = delete;
    ~dequeue()
    {
        delete[] buffer;
    }
    dequeue<T>()

    {
        last_index = 0;
        first_index = 0;
        size = 16;
        current_size = 0;
        buffer = new T [size];
    }
};
template <typename T>
/*Алгоритм работы пушбека и пушфронта
 * Проверка на заполненность текущего массива, если полон вызываем функцию увеличения.
 * Если мы пока ничего не записали:
 * Вначале поставим начало с концом на 0-ой элемент, т.к пока массив пустой(это условие) и запишем в конец элемент.
 * Если уже что-то есть:
 * Сдвинем хвост на один, если нет выхода за границу нуля,то прибавим размер массива и пойдем с другой стороны.
 * в конце увеличим текущий размер дека
 * Функция пушфронт работает аналогично.
 **/
int dequeue<T>::get_size()
{return current_size;}
template <typename T>
void dequeue<T>::push_back(T element) {
    if (current_size == size)
    {
        increase_size();
    }
    if (current_size == 0)
    {
        last_index = first_index = 0;
        buffer[last_index] = element;
    }
    else
    {
        last_index = (--last_index < 0) ? last_index + size : last_index;
        buffer[last_index] = element;
    }
    current_size++;
}
/*алгоритм работы попбека и попфронта
 * вначале проверка на попытку достать элемент из пустого дека
 * если он не пустой, то
 * Зафиксируем элемент(первый или последний), т.к дальше поменяем индекс
 * Если первый,последний индексы выходят за границу(первый в минус, второй в s-1 и дальше),то значит мы дошли до
 * конца и надо брать с другой стороны.При попфронте мы идем по массиву влево, уменьшая его при каждой операции.
 * В конце уменьшим текущий размер дека и вернем элемент.
 * */
template <class T>
T dequeue<T>::pop_front()
{
    assert(current_size > 0);
    T element = buffer[first_index];
    first_index = (--first_index < 0) ? first_index + size : first_index;
    current_size--;
    return element;
}
/*Алгоритм работы функции увеличения размера
 *данная функция вызывается в пуш-ах, когда текущий  размер стал равен размеру выделенного массива
 * Тогда
 * вначале увеличим размер в 2 раза и выделим новый массив в динамической памяти
 * Когда будем переносить элементы в новый массив, будем располагать их в правильном порядке, а именно, 0-ой элемент-это
 * конец очереди. Реализация такого метода такова:каждый раз, когда мы записали элемент с конца, прибавим к индексу
 * последнего единицу. Если мы дошли до конца первого массива(он равен size/2, т.к мы сделали увеличение вначале),
 * то продолжжаем с другой стороны(в этом заключается зацикленность буфера).Если же не дошли, то просто движемся вправо.
 * После переноса всех элементов поставим хвост очереди на 0-ой элемент, а голову на размер старого массива, минус 1
 * (нумерация с нуля).Получили очередь в правильном порядке, с которой продолжим работу.В конце удалим старый массив, и
 * поместим указатель старого массива на новый.
 * */
template <class T>
void dequeue<T>::increase_size()
{
    size *= 2;
    T* buffer2 = new T [size];
    for (int i = 0; i < current_size; i++)
    {
        buffer2[i] = buffer[last_index];
        last_index = (++last_index == size / 2) ? last_index - size / 2 : last_index;
    }
    last_index = 0;
    first_index = current_size - 1;
    delete[] buffer;
    buffer = buffer2;
}
template <class T>
T dequeue<T>::pop_back()
{
    assert(current_size > 0);
    int element = buffer[last_index];
    last_index = (++last_index == size) ? last_index - size : last_index;
    current_size--;
    return element;

}


template <class T>
void dequeue<T>::push_front(T element)
{
    if (current_size == size)
    {
        increase_size();
    }
    if (current_size == 0)
    {
        last_index = first_index = 0;
        buffer[last_index] = element;
    }
    else
    {
        first_index = (++first_index==size) ? first_index - size : first_index;
        buffer[first_index] = element;
    }
    current_size++;
}
template <class T>
T dequeue<T>::show()
{return buffer[first_index];}
template <class T>
void swap(T& a,T& b);
template <class T>
void swap(T& a,T& b)
{
    T temp;
    temp=a;
    a=b;
    b=temp;
}


template <class T>


struct node
{
    node(T element)
    {
        key = element;
        node<T> *left = nullptr;
        node<T> *right = nullptr;
    }

    const node &operator = (const node<T> & node1)
    {
        key = node1.key;
        left = node1.left;
        right = node1.right;
        return *this;
    }

    node()
    {
        key;
        node<T> *left = nullptr;
        node<T> *right = nullptr;
    }
    T key;
    node *left;
    node *right;
};


template <class T>
struct tree
{
    node<T> * root;
    tree()
    {root = nullptr;}
    void add(T element)
    {

        if (!root)
        {
            root = new node<T>(element);
            return;
        }
        else
        {
            //std::cout << root->key;
            node<T>* temp = root;
            while (temp != nullptr)
            {
                if ( isbigger (element, temp->key) )
                {
                    //std::cout << 'g';
                    if (temp->right == nullptr)
                    {
                        //std::cout << 'r';
                        temp->right = new node<T>(element);
                        return;
                    }


                    temp = temp->right;

                }
                else
                {
                    if (temp->left == nullptr)
                    {
                        temp->left = new node<T>(element);
                        return;
                    }

                    temp = temp->left;

                }
            }

        }
    }
    void preOrder(node<T> * start)
    {
        if (start == nullptr)
        {return;}
        dequeue<node<T>* > iterations;
        iterations.push_front(start);
        while(iterations.get_size() != 0)
        {
            start = iterations.pop_front();
            std::cout<<start->key<<" ";
            if ( start->right != nullptr )
            {
                iterations.push_front(start->right);
            }
            if (start->left != nullptr )
            {
                iterations.push_front(start->left);
            }
        }



    }

};

bool intBigger(const int & a,const int & b)
{return a > b;}




int main() {
    tree<int> Tree1;
    int size;
    std::cin>>size;
    int *tmpArray = new int [size];
    for(int i = 0; i < size; i++)
    {
        std::cin>>tmpArray[i];
    }
    for(int i = 0; i < size; i++)
    {Tree1.add(tmpArray[i]);}
    Tree1.preOrder(Tree1.root);
    return 0;
}