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


int Left=0, Right=1, Equal=2;

int trebuie_echilibrat,balance;
struct AVL_Tree
{
    int balance;
    int 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 == Right)
    {
        a->r = b->l;
        b->l = a;
        a->balance = b->balance = Equal;
        return b;
    }
    c = b->l;
    if(c->balance==Equal)
        {a->balance = Equal;
         b->balance = Equal;}

    else if(c->balance==Right)
        {a->balance = Left;
         b->balance = Equal;}
    else if(c->balance==Left)
        {a->balance = Equal;
         b->balance = Right;}

    a->r = c->l;
    b->l = c->r;
    c->balance = Equal;
    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 == Left)
    {
        a->l = b->r;
        b->r = a;
        a->balance = b->balance = Equal;
        return b;
    }
    c = b->r;
    if(c->balance==Equal)
        {a->balance = Equal;
         b->balance = Equal;}

    else if(c->balance==Right)
        {a->balance = Right;
         b->balance = Equal;}
    else if(c->balance==Left)
        {a->balance = Equal;
         b->balance = Left;}

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


AVL_Tree* inserare (AVL_Tree *t, int k)
{
    if (t == NULL)
    {
        t = new AVL_Tree;
        t->balance = Equal;
        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==Left)
            {t->balance = Equal;
             trebuie_echilibrat = 0;
             return t;}
        else if (t->balance==Equal)
            {t->balance = Right;
             return t;}
        else if (t->balance==Right)
            {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==Left)
            {trebuie_echilibrat = 0;
             return echilibrare_stanga (t);}
        else if (t->balance==Equal)
            {t->balance = Left;
             return t;}
        else if (t->balance==Right)
            {t->balance = Equal;
             trebuie_echilibrat = 0;
             return t;}

    }
  else
    {
        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()
{

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

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