#include<iostream>
#include<fstream>
using namespace std;

ifstream f("algsort.in");
ofstream g("algsort.out");

struct nod
{
 int key;
 int ech;
 nod *left, *right;
};
nod* avl=NULL;

void drum_maxim(nod* p,int &max,int lung)
{
    if(p!=NULL)
        {drum_maxim(p->right,max,lung+1);
        if((p->left==NULL)&&(p->right==NULL)&&(max<lung))
            max=lung;
        drum_maxim(p->left,max,lung+1);}
}

void fact_ech(nod *p)
{
    int h_left=1,h_right=1;

    if(p->left!=NULL) drum_maxim(p->left,h_left,1);
    else h_left=0;

    if(p->right!=NULL) drum_maxim(p->right,h_right,1);
    else h_right=0;
    p->ech=h_right-h_left;
}

nod* s_rot_right(nod *p)
{
    nod* q;
    q=p->left;
    p->left=q->right;
    q->right=p;
    fact_ech(p); fact_ech(q);
    p=q; return p;
}

nod* s_rot_left(nod *p)
{
    nod* q;
    q=p->right;
    p->right=q->left;
    q->left=p;
    fact_ech(p); fact_ech(q);
    p=q; return p;
}
nod* d_rot_right(nod *p)
{
    p->left=s_rot_left(p->left);
    p=s_rot_right(p);
    return p;
}
nod* d_rot_left(nod *p)
{
    p->right=s_rot_right(p->right);
    p=s_rot_left(p);
    return p;
}

nod* echilibreaza(nod *p)
{
    nod *w;
    fact_ech(p);
    if(p->ech==-2||p->ech==2)
    {
        if(p->ech==-2)
            {w=p->left;
            if (w->ech==1) p=d_rot_right(p);
            else p=s_rot_right(p);}
        else
            {w=p->right;
            if (w->ech==-1) p=d_rot_left(p);
            else p=s_rot_left(p);}

        p->right=echilibreaza(p->right);
        p->left=echilibreaza(p->left);
    }
    return p;
}

nod* insereaza(nod *p,int x)
{
    if(p==NULL)
        {p=new nod;
        p->key=x;
        p->ech=0;
        p->right=NULL;
        p->left=NULL;
        return p;}
    else
        {if(p->key>=x) p->left=insereaza(p->left,x);
        else p->right=insereaza(p->right,x);}

    return echilibreaza(p);
}

void afiseaza(nod* p)
{
    if(p==NULL) return;
    afiseaza(p->left);
    g<<p->key<<" ";
    afiseaza(p->right);
}

int main()
{
    int i,n,x;
    avl=new nod;
    avl=NULL;
    f>>n;

    for(i=1;i<=n;i++) {f>>x; avl=insereaza(avl,x);}

    afiseaza(avl);

    f.close();
    g.close();
    return 0;
}