#include <iostream>
#include <cstdio>
#include <stdlib.h>
using namespace std;

#define max(a,b) ((a) > (b) ? a : b)


struct node{
int key,h;
node * l, *r;
}*R,*NIL;

typedef struct node node ;

void init()
{
    R=NIL=(node*)malloc(sizeof(node));
    NIL->key=NIL->h=0;
    NIL->l=NIL->r=NULL;

}
inline int geth(node *n)
{
    return 1 + max(n->l->h, n->r->h);

}
node * LeftRotation(node *n)
{
    node *t = n->r;
    n->r=t->l;
    t->l = n;
    n->h = geth(n);
    t->h = geth(t);
    return t;

}
node* RightRotation(node *n)
{
    node *t = n->l;
    n->l=t->r;
    t->r=n;
    n->h = geth(n);
    t->h = geth(t);
    return t;

}
node* Balance(node *n)
{
    //n->h= geth(n);
    // If tree is left heavy
    if(n->l->h > n->r->h )
    {
        // if left subtree is right-heavy
        if(n->l->r->h > n->l->l->h + 1)
            n->l = LeftRotation(n->l);
        n = RightRotation(n);
    }
        // if tree is right heavy
    else
    {
        // if right subtree is left-heavy
        if(n->r->l->h > n->r->r->h +1 )
            n->r = RightRotation(n->r);
        n= LeftRotation(n);
    }
    return n;
}
node* Insert(node *n, int key)
{
    if(n==NIL)
    {
        n=(node *)malloc(sizeof(node));
        n->key=key;
        n->h=1;
        n->l = n->r = NIL;
        return n;
    }
    else if(key < n->key )
        n->l= Insert(n->l,key);
    else
        n->r= Insert(n->r,key);
    return Balance(n);
}


void inorderTraversal(node *n)
{
    if(n!=NIL)
    {
        inorderTraversal(n->l);
        printf("%d ",n->key);
        inorderTraversal(n->r);
    }
}


int search(node *n, int key)
{
    if(n==NIL) return 0;
    else if(n->key == key) return 1;
    else if(key < n->key)  return search(n->l,key);
    else return search(n->r,key);

}

int main()
{
    freopen("algsort.in","r",stdin);
    freopen("algsort.out","w",stdout);
    int i,nr,n;
    init();
    cin>>n;
    for(i=1 ; i<=n ;i++)
    {
        cin>>nr;
        R = Insert(R,nr);
    }
    inorderTraversal(R);

}