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

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

struct nod{int info; nod* fs; nod* fd; int ns; int nd; int poz;};

nod* prim=NULL;

void increase(nod* p)
{
    if(p!=NULL)
    {
        p->poz++;
        increase(p->fs);
        increase(p->fd);
    }
}

void insert(nod* p, int y)
{
    if(p->info>=y)
    {
        p->poz++;
        increase(p->fd);
        if(p->fs==NULL)
        {
            nod *np=new nod;
            np->info=y;
            np->fs=NULL;
            np->fd=NULL;
            np->ns=0;
            np->nd=0;
            p->fs=np;
            p->fs->poz=p->poz-1;
            p->ns=1;
        }
        else
        {
            insert(p->fs,y);
            p->ns=max(p->fs->ns,p->fs->nd)+1;
        }
    }

    else
        if(p->fd==NULL)
        {
            nod *np=new nod;
            np->info=y;
            np->fs=NULL;
            np->fd=NULL;
            np->ns=0;
            np->nd=0;
            p->fd=np;
            p->fd->poz=p->poz+1;
            p->nd=1;
        }
        else
        {
            insert(p->fd,y);
            p->nd=max(p->fd->ns,p->fd->nd)+1;
        }
}

void write(nod* p)
{
    if(p!=NULL)
    {
        write(p->fs);
        g<<p->info<<" ";
        write(p->fd);
    }
}


void rotleft(nod *&p)
{
    nod* a,*b,*c;
    a=p;
    b=p->fd;
    c=p->fd->fs;

    p=b;
    p->fs=a;
    p->fs->fd=c;

    p->fs->nd=p->ns;
    p->ns=max(p->fs->nd,p->fs->ns)+1;
}

void rotright(nod*& p)
{
    nod* a,*b,*c;
    a=p;
    b=p->fs;
    c=p->fs->fd;

    p=b;
    p->fd=a;
    p->fd->fs=c;

    p->fd->ns=p->nd;
    p->nd=max(p->fd->ns,p->fd->nd)+1;
}


void balance(nod* &p)
{
    if((p->ns >= 2)||(p->nd >= 2))
    {
        if(p->ns - p->nd >= 2)
            if(p->fs->ns - p->fs->nd > 0)
                {rotright(p); balance(p);}
            else
                {rotleft(p->fs); balance(p);}
        else
            if((p->nd - p->ns >= 2))
                if(p->fd->nd - p->fd->ns > 0)
                    {rotleft(p); balance(p);}
                else
                    {rotright(p->fd); balance(p);}
            else
            {
                balance(p->fs);
                balance(p->fd);
            }

            p->ns=max(p->fs->ns,p->fs->nd)+1;
            p->nd=max(p->fd->ns,p->fd->nd)+1;
    }
}

int search(nod* p,int k)
{
    if(p->poz==k)return p->info;
    else if(p->poz>k) return search(p->fs,k);
        else return search(p->fd,k);
}

int main()
{
    int i,n,x;
    f>>n>>x;
    nod *p=new nod;

    p->info=x;
    p->fs=NULL;
    p->fd=NULL;
    prim=p;
    p->ns=0;
    p->nd=0;
    p->poz=1;

    for(i=1;i<n;i++) {f>>x; insert(prim, x);}
    balance(prim);
    write(prim);

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