#include <iostream>
#include <fstream>
#include<cstring>
#include<cmath>
using namespace std;
struct nod
{
    int x, h, c;
    nod *st, *dr;
};
nod *root;
ofstream g("algsort.out");
int height(struct nod *n)
{
    int dr, st;
    if (n->dr==NULL) dr=0;
        else dr=n->dr->h;
    if (n->st==NULL) st=0;
        else st=n->st->h;
    return 1+max(st, dr);
}
int alt(struct nod *n)
{
    int dr, st;
    if (n->dr==NULL) dr=0;
        else dr=n->dr->h;
    if (n->st==NULL) st=0;
        else st=n->st->h;
    return st-dr;
}

struct nod* left_rotate(nod* x)
{
    nod *r;

    r = x->dr;
    x->dr = r->st;
    r->st = x;

    x->h=height(x);
    r->h=height(r);
    return r;
}
struct nod* right_rotate(nod* x)
{
    nod *l = x->st;
    x->st = l->dr;
    l->dr = x;

    x->h=height(x);
    l->h=height(l);
    return l;
}

nod* balance(nod* n)
{
    n->h = height(n);
    int b = alt(n);
    if (b>1)
    {
        if (alt(n->st)<0)
            n->st = left_rotate(n->st);
        return right_rotate(n);
    }

    if (b<-1)
     {
         if (alt(n->dr)>0)
            n->dr = right_rotate(n->dr);
         return left_rotate(n);
     }
     return n;
}


struct nod* inserare(struct nod *n, int val)
{

    if (n==NULL) {n=new nod; n->x=val; n->h=1; n->st=NULL; n->dr=NULL; n->c=1 ; return n;}
    else
        if (n->x > val) n->st=inserare(n->st, val);
            else if (n->x < val) n->dr=inserare(n->dr, val);
                else n->c++;
    return balance(n);
}

void inordine(nod *n)
{
    if (n==NULL) return;
    inordine(n->st);
    while (n->c--) g<<n->x<<' ';
    inordine(n->dr);
}

int main()
{
    int n, nr, i, j, x;
    ifstream f("algsort.in");
    f>>n;
    root=new nod;
    root=NULL;
    for (i=1;i<=n;i++)
    {
        f>>x;
        root=inserare(root, x);
    }
    inordine(root);
    g<<'\n';
}