#include <stdio.h>
#include <algorithm>
#include <cmath>

using namespace std;

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

nod* prim=NULL;
FILE *f;

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

void insereaza(nod* p, int y)
{
    if(p->info>=y)
    {
        p->poz++;
        mareste(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
        {
            insereaza(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
        {
            insereaza(p->fd,y);
            p->nd=max(p->fd->ns,p->fd->nd)+1;
        }
}

void afiseaza(nod* p)
{
    if(p!=NULL)
    {

        afiseaza(p->fs);
        fprintf(f,"%i ",p->info);
        afiseaza(p->fd);
    }
}


void lrot(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 rrot(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 echilibreaza(nod* &p)
{
    if((p->ns >= 2)||(p->nd >= 2))
    {
        if(p->ns - p->nd >= 2)
            if(p->fs->ns - p->fs->nd > 0)
                {rrot(p);echilibreaza(p);}
            else
                {lrot(p->fs);echilibreaza(p);}
        else
            if((p->nd - p->ns >= 2))
                if(p->fd->nd - p->fd->ns > 0)
                    {lrot(p);echilibreaza(p);}
                else
                    {rrot(p->fd);echilibreaza(p);}
            else
            {
                echilibreaza(p->fs);
                echilibreaza(p->fd);
            }

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

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

int main()
{
    int i,n,x;
    f=fopen("algsort.in","r");
    fscanf(f,"%i",&n);
    fscanf(f,"%i",&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++)
    {
        fscanf(f,"%i",&x);
        insereaza(prim, x);

    }
    fclose(f);
    echilibreaza(prim);
    f=fopen("algsort.out","w");
    afiseaza(prim);
    fclose(f);
    return 0;
}