// AVL sort
#include <fstream>

using namespace std;

struct Node
{
    int key;
    int height;
    Node *left;
    Node *right;
};

Node * insert(Node *&root, int value);
int getHeight(Node *root);
int max(int a, int b);
Node * rotateRight(Node *&root);
Node * rotateLeft(Node *&root);
Node * getMax(Node *root);
Node * getMin(Node *root);
Node * del(Node *&root, int value);

int main()
{
    int N, i, x;
    ifstream f("algsort.in");
    f >> N;
    Node *root = NULL;
    for (i = 0; i < N; i++)
    {
        f >> x;
        root = insert(root, x);
    }
    f.close();

    ofstream g("algsort.out");
    for (i = 0; i < N; i++)
    {
        x = getMin(root)->key;
        g << x << " ";
        root = del(root, x);
    }
    g.close();

    return 0;
}

Node * insert(Node *&root, int value)
{
    if (!root)
    {
        Node *newEntry = new Node;
        newEntry->left = NULL;
        newEntry->right = NULL;
        newEntry->key = value;
        newEntry->height = 0;
        return newEntry;
    }
    else
    {
        if (root->key > value)
            root->left = insert(root->left, value);
        else
            root->right = insert(root->right, value);

        root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
        int balance = getHeight(root->left) - getHeight(root->right);

        if (balance == 2) // Left Left || Left Right
        {
            if (value < root->left->key) // Left Left
                return rotateRight(root);
            else
            {
                root->left = rotateLeft(root->left);
                return rotateRight(root);
            }
        }
        else if (balance == -2) // Right Right || Right Left
        {
            if (value >= root->right->key) // Right Right
                return rotateLeft(root);
            else // Right Left
            {
                root->right = rotateRight(root->right);
                return rotateLeft(root);
            }
        }

        return root;
    }
}

int getHeight(Node *root)
{
    if (!root)
        return -1;
    else
        return root->height;
}

int max(int a, int b)
{
    if (a > b)
        return a;

    return b;
}

Node * rotateRight(Node *&root)
{
    Node *z = root;
    Node *y = z->left;
   // Node *x = y->left;

    root = y;
    z->left = y->right;
    y->right = z;

    z->height = max(getHeight(z->left), getHeight(z->right)) + 1;
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;

    return root;
}

Node * rotateLeft(Node *&root)
{
    Node *z = root;
    Node *y = z->right;
    //Node *x = y->right;

    root = y;
    z->right = y->left;
    y->left = z;

    z->height = max(getHeight(z->left), getHeight(z->right)) + 1;
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;

    return root;
}

Node * getMax(Node *root)
{
    if (root)
    {
        if (root->right)
            return getMax(root->right);
        else
            return root;
    }

    return NULL;
}

Node * getMin(Node *root)
{
    if (root)
    {
        if (root->left)
            return getMin(root->left);
        else
            return root;
    }

    return NULL;
}

Node * del(Node *&root, int value)
{
    if (root)
    {
        if (root->key < value)
            root->right = del(root->right, value);
        else if (root->key > value)
            root->left = del(root->left, value);
        else if (root->key == value)
        {
            if (!root->left && !root->right)
            {
                delete root;
                return NULL;
            }
            else if (!root->left)
            {
                Node *tmp = root->right;
                delete root;
                return tmp;
            }
            else if (!root->right)
            {
                Node *tmp = root->left;
                delete root;
                return tmp;
            }
            else
            {
                Node *tmp = getMax(root->left);
                root->key = tmp->key;
                root->left = del(root->left, tmp->key);
            }
        }

        root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
        int balance = getHeight(root->left) - getHeight(root->right);

        if (balance == 2) // LL || LR
        {
            if (getHeight(root->left->left) > getHeight(root->left->right))
                return rotateRight(root);
            else
            {
                root->left = rotateLeft(root->left);
                return rotateRight(root);
            }
        }
        else if (balance == -2) // RR || RL
        {
            if (getHeight(root->right->right) > getHeight(root->right->left))
                return rotateLeft(root);
            else
            {
                root->right = rotateRight(root->right);
                return rotateLeft(root);
            }
        }
    }

    return root;
}