#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

struct AVL_Node{
    int info;
    AVL_Node * left, * right;
};

AVL_Node * LL_Rotation(AVL_Node *Parent)
{
    AVL_Node * temp;
    temp = Parent -> left;
    Parent -> left = temp -> right;
    temp -> right = Parent;
    return temp;
}

AVL_Node * RR_Rotation(AVL_Node *Parent)
{
    AVL_Node * temp;
    temp = Parent -> right;
    Parent -> right = temp -> left;
    temp -> left = Parent;
    return temp;
}

AVL_Node * LR_Rotation(AVL_Node *Parent)
{
    AVL_Node * temp;
    temp = Parent -> left;
    Parent -> left = RR_Rotation(temp);
    return LL_Rotation(Parent);
}

AVL_Node * RL_Rotation(AVL_Node *Parent)
{
    AVL_Node * temp;
    temp = Parent -> right;
    Parent -> right = LL_Rotation(temp);
    return RR_Rotation(Parent);
}

int height(AVL_Node *Root)
{
    int h = 0;
    if(Root)
    {
        int height_left = height(Root -> left);
        int height_right = height(Root -> right);
        h = max(height_left, height_right) + 1;
    }
    return h;
}

int diff(AVL_Node *Root)
{
    if(Root)
    {
        int height_left = height(Root -> left);
        int height_right = height(Root -> right);
        return height_left - height_right;
    }
    return 0;
}

AVL_Node * Balance(AVL_Node *Root)
{
    int dif = diff(Root);
    if (dif < -1)
    {
        if (diff(Root -> right) < 0)
            Root = RR_Rotation(Root);
        else
            Root = RL_Rotation(Root);
    }
    else
        if (dif > 1)
        {
            if(diff(Root -> left) > 0)
                Root = LL_Rotation(Root);
            else
                Root = LR_Rotation(Root);
        }
    return Root;
}

AVL_Node * insert(AVL_Node *Root, int key)
{
    if (Root == NULL)
    {
        Root = new AVL_Node;
        Root -> info = key;
        Root -> left = NULL;
        Root -> right = NULL;
        return Root;
    }
    else
    {
        if (key < Root -> info)
        {
            Root -> left = insert(Root -> left, key);
            Root = Balance(Root);
        }
        else
        {
            Root -> right = insert(Root -> right, key);
            Root = Balance(Root);
        }
    }
    return Root;
}

void sort(AVL_Node *node)
{
    if (node)
    {
        if (node -> left != NULL)
            sort(node -> left);
        out << node -> info << " ";
        if (node -> right != NULL)
            sort(node -> right);
    }
}

AVL_Node *AVL;
int n;

int main()
{
    in >> n;
    int x;
    for (int i = 1; i <= n; i++)
    {
        in >> x;
        AVL = insert(AVL, x);
    }
    in.close();
    sort(AVL);
    out.close();
    return 0;
}