#include <cstdio>
#include <algorithm>

using namespace std;

class AVL{
public:
    int value,height;
    AVL *st,*dr;
    AVL(int value,int height,AVL *st,AVL *dr){
        this->value = value;
        this->height = height;
        this->st = st;
        this->dr = dr;
    }
}*root,*nil;

void init(){
    root = nil = new AVL(0,0,NULL,NULL);
}

void Rotate_left(AVL *&n)
{
    AVL *aux = n->st;
    n->st = aux->dr;
    aux->dr = n;
    n = aux;
    aux->height = max(aux->st->height,aux->dr->height) + 1;
    n -> height = max(n->st->height,n->dr->height)+1;
}
void Rotate_right(AVL *&n)
{
    AVL *aux = n->dr;
    n->dr = aux->st;
    aux->st = n;
    n = aux;
    aux->height = max(aux->st->height,aux->dr->height) + 1;
    n -> height = max(n->st->height,n->dr->height)+1;
}

void Balance(AVL *&n)
{
    n->height = max(n->st->height,n->dr->height) + 1;
    if(n->st->height > n->dr->height + 1)
    {
        if(n->st->st->height < n->st->dr->height)
            Rotate_right(n->st);
        Rotate_left(n);
    }
    else
        if(n->st->height < n->dr->height + 1)
        {
            if(n->dr->dr->height < n->dr->st->height)
                Rotate_left(n->dr);
            Rotate_right(n);
        }
}

void Delete(int value,AVL *&n)
{
    if(n == nil) return;
    if(n->value > value)
        Delete(value,n->st);
    else
        if(n->value < value)
            Delete(value,n->dr);
        else
            if(n->st == nil && n->dr == nil)
            {
                delete n; n = nil;
                return;
            }
}

void Insert(int value,AVL *&n)
{
    if(n == nil){
        n = new AVL(value,1,nil,nil);
        return;
    }
    if(n->value > value)
        Insert(value,n->st);
    else
        Insert(value,n->dr);
    Balance(n);
}

void srd(AVL *nod){
    if(nod == nil) return;
    srd(nod->st);
    printf("%d ",nod->value);
    srd(nod->dr);

}

int main()
{
    freopen("algsort.in","r",stdin);
    freopen("algsort.out","w",stdout);
    init();
    int N,x;
    scanf("%d",&N);
    for(int i = 1; i <= N; ++i){
        scanf("%d",&x);
        Insert(x,root);
    }
    srd(root);
    return 0;
}