#include <iostream>
#include <fstream>

using namespace std;

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

struct nod {int info;
            nod* right;
            nod* left;
            int factor;
            } *root;
void drum_max(nod *p, int &max, int lung)
{
    if(p!=NULL)
    {
        drum_max(p->right,max, lung+1);
        if(p->left==NULL && p->right==NULL && max<lung)
            max=lung;
        drum_max(p->left,max,lung+1);
    }
}
void calcul_factor_echilibru (nod*p)
{
    int h_left=0, h_right=0;
    if(p->left!=NULL)
        drum_max(p->left,h_left,0);
    else h_left=0;
    if(p->right!=NULL)
        drum_max(p->right, h_right,0);
    else h_right=0;
    p->factor=h_right-h_left;
}
nod *s_rot_right(nod *p)
{
    nod *q;
    q=p->left;
    p->left=q->right;
    q->right=p;
    calcul_factor_echilibru(p);
    calcul_factor_echilibru(q);
    p=q;
    return p;
}
nod *s_rot_left(nod *p)
{
    nod *q;
    q=p->right;
    p->right=q->left;
    q->left=p;
    calcul_factor_echilibru(p);
    calcul_factor_echilibru(q);
    p=q;
    return p;
}
nod *d_rot_right(nod *p)
{
    p->left=s_rot_left(p->left);
    p=s_rot_right(p);
    return p;
}
nod *d_rot_left(nod *p)
{
    p->right=s_rot_right(p->right);
    p=s_rot_left(p);
    return p;
}
nod *echilibrare(nod *p)
{
    nod *w;
    calcul_factor_echilibru(p);
    if(p->factor==-2)
    {
        w=p->left;
        if(w->factor==1)
            p=d_rot_right(p);
        else p=s_rot_right(p);
    }
    else if(p->factor==2)
    {
        w=p->right;
        if(w->factor==-1)
            p=d_rot_left(p);
        else p=s_rot_left(p);
    }
    return p;
}
nod *creare()
{
    nod *p,*q,*r;
    int x;
    while(f>>x)
    {
        p=new nod;
        p->info=x;
        p->left=NULL;
        p->right=NULL;
        if(root==NULL)
            root=p;
        else {
                q=root;
                while(q!=NULL)
                {
                    r=q;
                    if(p->info<q->info)
                        q=q->left;
                    else q=q->right;
                }
                if(p->info<r->info)
                    r->left=p;
                else r->right=p;
            }
        echilibrare(root);
    }
    return root;
    }
nod *insereaza(nod* &p, int x)
{
    if(p==NULL)
    {
        p=new nod;
        p->info=x;
        p->factor=0;
        p->right=NULL;
        p->left=NULL;
        return p;
    }
    else
    {
        if(x<p->info)
            p->left=insereaza(p->left,x);
        else p->right=insereaza(p->right, x);
    }
    echilibrare(p);
    return p;
}
void srd(nod *p)
{
    if(p->left!=NULL)
        srd(p->left);
    g<<p->info<<' ';
    if(p->right!=NULL)
        srd(p->right);
}
int main()
{
    int n,x;
    root=NULL;
    for(int i=1;i<=n;i++)
    {
        f>>x;
        insereaza(root,x);
    }
    srd(root);
    return 0;
}