#include <fstream>
#include <cmath>

using namespace std;

struct node
{
    int key;
    int h;
    int w;
    int app;
    node *left, *right;
};

node *root;

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

int HEIGHT(struct node *n)
{
    int right, left;
    if (n->right==NULL)
        right=0;
    else
        right=n->right->h;
    if (n->left==NULL)
        left=0;
    else
        left=n->left->h;
    return 1+max(left, right);
}
int bfactor(struct node *n)
{
    int right, left;
    if (n->right==NULL)
        right=0;
    else
        right=n->right->h;
    if (n->left==NULL)
        left=0;
    else
        left=n->left->h;
    return left-right;
}
int weight(struct node *n)
{
    if (n->right==NULL && n->left==NULL)
        return 1;

    int right, left;

    if (n->right==NULL)
        right=1;
    else
        right=n->right->w;

    if (n->left==NULL)
        left=1;
    else
        left=n->left->w;

    return left+right+1;
}
node* left_rotate(node *x)
{
    node *r;

    r = x->right;
    x->right = r->left;
    r->left = x;

    x->h=HEIGHT(x);
    x->w=weight(x);

    r->w=weight(r);
    r->h=HEIGHT(r);
    return r;
}
node* right_rotate(node *x)
{
    node *l = x->left;
    x->left = l->right;
    l->right = x;

    x->h=HEIGHT(x);
    x->w=weight(x);

    l->w=weight(l);
    l->h=HEIGHT(l);
    return l;
}

node* balance(node *n)
{
    n->h = HEIGHT(n);
    n->w = weight(n);
    int b = bfactor(n);
    if (b>1)
    {
        if (bfactor(n->left)<0)
            n->left = left_rotate(n->left);
        return right_rotate(n);
    }

    if (b<-1)
     {
         if (bfactor(n->right)>0)
            n->right = right_rotate(n->right);
         return left_rotate(n);
     }
     return n;
}


node* inserare(struct node *n, int val)
{

    if (n==NULL)
    {
        n=new node;
        n->key=val;
        n->h=1;
        n->w=1;
        n->left=NULL;
        n->right=NULL;
        n->app=1 ;
        return n;
    }
    else
        if (n->key > val)
            n->left=inserare(n->left, val);
        else
            if (n->key < val)
                n->right=inserare(n->right, val);
            else
                n->app++;
    return balance(n);
}

void inordine(node *n)
{
    if (n==NULL) return;
    inordine(n->left);
    while (n->app--) g<<n->key<<' ';
    inordine(n->right);
}

int main()
{
    int n, i, x;

    f>>n;
    root=new node;
    root=NULL;
    for (i=1;i<=n;i++)
    {
        f>>x;
        root=inserare(root, x);
    }
    inordine(root);
    return 0;
}