#include <iostream>
#include <random>

using namespace std;

struct Nod
{
    int val, prioritate;
    Nod *left = nullptr;
    Nod *right = nullptr;

    Nod(int nr) 
    {
        val=nr;
        prioritate=rand();
    }
};
pair<Nod*, Nod*> split(Nod* nod, int val)
{
    if(nod==nullptr)
    {
        return {nullptr,nullptr};
    }
    pair<Nod*, Nod*> aux;
    if(nod->val<=val) ///subarborele stang
    {
        aux = split(nod->right,val);
        nod->right = aux.first;
        return {nod, aux.second};
    }
    else ///subarborele drept
    {
        aux = split(nod->left,val);
        nod->left = aux.second;
        return {aux.first, nod};
    }
}
Nod* join(Nod* left, Nod* right)
{
    if(left==nullptr)
        return right;
    if(right==nullptr)
        return left;

    if(left->prioritate > right->prioritate)
    {
        left->right=join(left->right,right);
        return left;
    }
    else
    {
        right->left=join(left,right->left);
        return right;
    }
}
Nod* insert(Nod* root, int val) 
{
    Nod* nod_nou = new Nod(val);
    pair<Nod*,Nod*> aux;
    aux = split(root,val);
    return join(aux.first, join(nod_nou, aux.second));
}
void afis(Nod* root)
{
    if(root==nullptr)
        return ;
    afis(root->left);
    cout<<root->val<<" ";
    afis(root->right);
}

int main()
{
    Nod* root = nullptr;
    int n,i,x;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>x;
        root = insert(root, x);
    }
    afis(root);
    return 0;
}