//Mares Medar Razvan - Grupa 141
//Algoritm AVL
#include <iostream>
#include <cctype>
#include <stdlib.h>
#include <fstream>
using namespace std;
int n,i,a;
ifstream f("algsort.in");
ofstream g("algsort.out");
struct node{
    int inf;
    node *left,*right;
    int height;
    };
typedef struct node *nodeptr;
void insert(int,nodeptr &);
void del(int, nodeptr &);
int deletemin(nodeptr &);
void find(int,nodeptr &);
nodeptr findmin(nodeptr);
nodeptr findmax(nodeptr);
void makeempty(nodeptr &);
void copy(nodeptr &,nodeptr &);
nodeptr nodecopy(nodeptr &);
void rsd(nodeptr);
void srd(nodeptr);
void sdr(nodeptr);
int bsheight(nodeptr);
nodeptr srl(nodeptr &);
nodeptr drl(nodeptr &);
nodeptr srr(nodeptr &);
nodeptr drr(nodeptr &);
int max(int,int);
int nonodes(nodeptr);
void insert(int x,nodeptr &p){
    if (p == NULL){
        p = new node;
        p->inf = x;
        p->left=NULL;
        p->right = NULL;
        p->height=0;
        if (p==NULL)
            cout<<"Nu mai este spatiu"<<endl;
    }
    else{
        if (x<p->inf){
            insert(x,p->left);
            if ((bsheight(p->left) - bsheight(p->right))==2)
                if (x < p->left->inf)
                    p=srl(p);
                else
                    p = drl(p);
            }
        else if (x>p->inf){
            insert(x,p->right);
            if ((bsheight(p->right)-bsheight(p->left))==2)
                if (x > p->right->inf)
                    p=srr(p);
                else
                    p = drr(p);
            }
        else
            cout<<"Elementul exista deja."<<endl;
    }
    int m,n,d;
    m=bsheight(p->left);
    n=bsheight(p->right);
    d=max(m,n);
    p->height = d + 1;
}
void copy(nodeptr &p,nodeptr &p1){
    makeempty(p1);
    p1 = nodecopy(p);
}
void makeempty(nodeptr &p){
    nodeptr d;
    if (p != NULL){
        makeempty(p->left);
        makeempty(p->right);
        d=p;
        free(d);
        p=NULL;
    }
}
nodeptr nodecopy(nodeptr &p){
    nodeptr temp;
    if (p==NULL)
        return p;
    else{
        temp = new node;
        temp->inf= p->inf;
        temp->left = nodecopy(p->left);
        temp->right = nodecopy(p->right);
        return temp;
    }
}
void srd(nodeptr p){
    if (p!=NULL){
    srd(p->left);
    g<<p->inf<<" ";
    srd(p->right);
    }
}
int max(int value1, int value2){
    return ((value1 > value2) ? value1 : value2);
}
int bsheight(nodeptr p){
    int t;
    if (p == NULL)
        return -1;
    else{
        t = p->height;
        return t;
        }
}
nodeptr srl(nodeptr &p1){
    nodeptr p2;
    p2 = p1->left;
    p1->left = p2->right;
    p2->right = p1;
    p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
    p2->height = max(bsheight(p2->left),p1->height) + 1;
    return p2;
}
nodeptr srr(nodeptr &p1){
    nodeptr p2;
    p2 = p1->right;
    p1->right = p2->left;
    p2->left = p1;
    p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
    p2->height = max(p1->height,bsheight(p2->right)) + 1;
    return p2;
}
nodeptr drl(nodeptr &p1){
    p1->left=srr(p1->left);
    return srl(p1);
}
nodeptr drr(nodeptr &p1){
    p1->right = srl(p1->right);
    return srr(p1);
}
int nonodes(nodeptr p){
    int count=0;
    if (p!=NULL){
        nonodes(p->left);
        nonodes(p->right);
        count++;
    }
    return count;
}
int main(){
    nodeptr root;
    root=NULL;
    f>>n;
    for(i=1;i<=n;i++){
        f>>a;
        insert(a,root);
    }
    srd(root);
}