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

using namespace std;

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

nod v[500000];
int prim=0, k=1;
FILE *f;

void mareste_poz(int p)
{
    if(p!=-1)
    {
        v[p].poz++;
        mareste_poz(v[p].fs);
        mareste_poz(v[p].fd);
    }
}

void refa_n(int p)
{
    if(p!=-1)
    {
        if(v[p].fs!=-1)
            v[p].ns=max(v[v[p].fs].ns,v[v[p].fs].nd)+1;
        else
            v[p].ns=0;
        if(v[p].fd!=-1)
            v[p].nd=max(v[v[p].fd].ns,v[v[p].fd].nd)+1;
        else
            v[p].nd=0;
        refa_n(v[p].t);
    }
}

void lrot(int &p)
{
    int a=p;
    int c=v[p].fd;
    int b=v[v[p].fd].fs;

    if(v[v[p].t].fs==p)
        v[v[p].t].fs=c;
    else
        v[v[p].t].fd=c;

    v[c].t=v[a].t;
    v[c].fs=a;

    v[a].fd=b;
    v[a].t=c;

    if(b!=-1)
    {
        v[b].t=a;
        refa_n(b);
    }
        else
        refa_n(a);

    if(v[c].t==-1)
        prim=c;

    p=c;
}

void rrot(int &p)
{
    int a=p;
    int c=v[p].fs;
    int b=v[v[p].fs].fd;

    if(v[v[p].t].fs==p)
        v[v[p].t].fs=c;
    else
        v[v[p].t].fd=c;

    v[c].t=v[a].t;
    v[c].fd=a;

    v[a].fs=b;
    v[a].t=c;

    if(b!=-1)
    {
        v[b].t=a;
        refa_n(b);
    }
        else
        refa_n(a);

    if(v[c].t==-1)
        prim=c;

    p=c;
}


void echilibreaza(int p)
{
    if(p!=-1)
    {
        if((v[p].ns >= 2)||(v[p].nd >= 2))
            if(v[p].ns - v[p].nd >= 2)
            {
                if(v[v[p].fs].ns < v[v[p].fs].nd)
                    lrot(v[p].fs);
                rrot(p);
            }
            else
                if((v[p].nd - v[p].ns >= 2))
                {
                    if(v[v[p].fd].nd < v[v[p].fd].ns)
                        rrot(v[p].fd);
                    lrot(p);
                }
        echilibreaza(v[p].t);
    }
}

void insereaza(int p, int y)
{
    if(v[p].info>=y)
    {
        v[p].poz++;
        mareste_poz(v[p].fd);
        if(v[p].fs==-1)
        {
            v[k].info=y;v[k].fs=-1;v[k].fd=-1;v[k].ns=0;v[k].nd=0;v[k].t=p;
            v[p].fs=k;
            v[k++].poz=v[p].poz-1;
            v[p].ns=1;
            refa_n(v[p].t);
            echilibreaza(v[p].t);
        }
        else
        {
            insereaza(v[p].fs,y);
        }
    }
    else
        if(v[p].fd==-1)
        {
            v[k].info=y;v[k].fs=-1;v[k].fd=-1;v[k].ns=0;v[k].nd=0;v[k].t=p;
            v[p].fd=k;
            v[k++].poz=v[p].poz+1;
            v[p].nd=1;
            refa_n(v[p].t);
            echilibreaza(v[p].t);
        }
        else
        {
            insereaza(v[p].fd,y);
        }
}

void afiseaza(int p)
{
    if(p!=-1)
    {
        afiseaza(v[p].fs);
        fprintf(f, "%d ", v[p]);
        afiseaza(v[p].fd);
    }
}

void insereaza_prim(int x)
{
    prim=0;
    v[prim].info=x;
    v[prim].fs=-1;
    v[prim].fd=-1;
    v[prim].ns=0;
    v[prim].nd=0;
    v[prim].poz=1;
    v[prim].t=-1;
}

int main()
{
    int i,n,x;
    f=fopen("algsort.in","r");
    fscanf(f, "%d", &n);
    fscanf(f, "%d", &x);
    insereaza_prim(x);
    for(i=1; i<n; i++)
    {
        fscanf(f, "%i", &x);
        insereaza(prim, x);
    }
    fclose(f);
    f=fopen("algsort.out","w");
    afiseaza(prim);
    fclose(f);
    return 0;
}