#include<iostream>
#include<fstream>
using namespace std;
ifstream f("algsort.in");
ofstream g("algsort.out");



long trebuie_echilibrat,balance;
struct AVL_Tree
{
    long balance;
    long key;
    AVL_Tree *l, *r;
};
AVL_Tree* AVL=NULL;

AVL_Tree* echilibrare_dreapta (AVL_Tree *a)
{
    AVL_Tree *b, *c;
    b = a->r;
    if (b->balance == 1)
    {
        a->r = b->l;
        b->l = a;
        a->balance = b->balance = 2;
        return b;
    }
    c = b->l;
    if(c->balance==2)
        {a->balance = 2;
         b->balance = 2;}

    else if(c->balance==1)
        {a->balance = 0;
         b->balance = 2;}
    else if(c->balance==0)
        {a->balance = 2;
         b->balance = 1;}

    a->r = c->l;
    b->l = c->r;
    c->balance = 2;
    c->l = a;
    c->r = b;
    return c;
}

AVL_Tree* echilibrare_stanga (AVL_Tree *a)
{
    AVL_Tree *b, *c;
    b = a->l;
    if (b->balance == 0)
    {
        a->l = b->r;
        b->r = a;
        a->balance = b->balance = 2;
        return b;
    }
    c = b->r;
    if(c->balance==2)
        {a->balance = 2;
         b->balance = 2;}

    else if(c->balance==1)
        {a->balance = 1;
         b->balance = 2;}
    else if(c->balance==0)
        {a->balance = 2;
         b->balance = 0;}

    a->l = c->r;
    b->r = c->l;
    c->balance = 2;
    c->r = a;
    c->l = b;
    return c;
}


AVL_Tree* inserare (AVL_Tree *t, long k)
{
    if (t == NULL)
    {
        t = new AVL_Tree;
        t->balance = 2;
        t->key = k;
        t->l = t->r = NULL;
        trebuie_echilibrat = 1;
        return t;
    }
    if (k >= t->key)
    {
        t->r = inserare (t->r, k);
        if (!trebuie_echilibrat) return t;

        if (t->balance==0)
            {t->balance = 2;
             trebuie_echilibrat = 0;
             return t;}
        else if (t->balance==2)
            {t->balance = 1;
             return t;}
        else if (t->balance==1)
            {trebuie_echilibrat = 0;
             return echilibrare_dreapta (t);}

    }
    else if (k < t->key)
    {
        t->l = inserare (t->l, k);
        if (!trebuie_echilibrat) return t;

        if (t->balance==0)
            {trebuie_echilibrat = 0;
             return echilibrare_stanga (t);}
        else if (t->balance==2)
            {t->balance = 0;
             return t;}
        else if (t->balance==1)
            {t->balance = 2;
             trebuie_echilibrat = 0;
             return t;}

    }

    {
        trebuie_echilibrat = 0;
        return t;
    }
}


void afiseaza(AVL_Tree *t)
{
    if(t==NULL) return;
    afiseaza(t->l);
    g<<t->key<<" ";
    afiseaza(t->r);
}

int main()
{

    long i,n;
    long x;
    f>>n;
    for(i=1;i<=n;i++)
    {f>>x;
    AVL=inserare (AVL,x); }
    afiseaza(AVL);

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