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

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

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

int height(nod *p)
{
    int dr,st;

    if(p->right==NULL) dr=0;
    else dr=p->right->h;

    if(p->left==NULL) st=0;
    else st=p->left->h;

    return 1+max(st,dr);
}
int fact_ech(nod *p)
{
    int dr,st;

    if (p->right==NULL) dr=0;
    else dr=p->right->h;

    if (p->left==NULL) st=0;
    else st=p->left->h;

    return dr-st;
}

nod* s_rot_right(nod *p)
{
    nod* q;

    q=p->left;
    p->left=q->right;
    q->right=p;

    p->h=height(p);
    q->h=height(q);
    p=q; return p;
}

nod* s_rot_left(nod *p)
{
    nod* q;

    q=p->right;
    p->right=q->left;
    q->left=p;

    p->h=height(p);
    q->h=height(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;

    p->h=height(p);
    int k=fact_ech(p);

    if(k==-2)
        {w=p->left;
        if (fact_ech(w)==1) p=d_rot_right(p);
        else p=s_rot_right(p);}
    else if(k==2)
        {w=p->right;
        if (fact_ech(w)==-1) p=d_rot_left(p);
        else p=s_rot_left(p);}

    return p;
}

nod* insereaza(nod *p,int x)
{
    if(p==NULL)
        {p=new nod;
        p->key=x;
        p->h=1;
        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;
    f>>n;

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

    afiseaza(avl);

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