#include <iostream>
#include <fstream>

using namespace std;

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

struct Item
{
    int val;
    int height;

    Item *left, *right;
};

//
// balance
//

int getBal(Item *nod)
{
    int l = (nod->left) ? nod->left->height : 0;
    int r = (nod->right) ? nod->right->height : 0;

    return r - l;
}

void setHeight(Item *nod)
{
    int l = (nod->left) ? nod->left->height : 0;
    int r = (nod->right) ? nod->right->height : 0;
    nod->height = 1 + max(l, r);
}

void singleRight(Item *&nod)
{
    Item *p = nod, *q = nod->left;

    p->left = p->left->right;
    setHeight(p);

    q->right = p;
    nod = q;

    setHeight(nod);
}

void singleLeft(Item *&nod)
{
    Item *p = nod, *q = nod->right;

    p->right = p->right->left;
    setHeight(p);

    q->left = p;
    nod = q;

    setHeight(nod);
}

void doubleRight(Item *&nod)
{
    singleLeft(nod->left);
    singleRight(nod);
}

void doubleLeft(Item *&nod)
{
    singleRight(nod->right);
    singleLeft(nod);
}

void balNode(Item *&nod)
{
    int locBal = getBal(nod);

    if (locBal > 1) //is right heavy
    {
        int rightBal = 0;
        if (nod->right)
            rightBal = getBal(nod->right);

        if (rightBal < 0) //right node is left heavy
        {
            doubleLeft(nod);
        }
        else
        {
            singleLeft(nod);
        }
    }
    else if (locBal < -1)
    {
        int leftBal = 0;
        if (nod->left)
            leftBal = getBal(nod->left);

        if (leftBal > 0) //left node is right heavy
        {
            doubleRight(nod);
        }
        else
        {
            singleRight(nod);
        }

    }

    setHeight(nod);
}

//
// Functii insertie
//
void singleInsert(Item *&nod, int val, Item *par)
{
    nod = new Item;

    nod->val = val;
    nod->height = 1;
    nod->left = NULL;
    nod->right = NULL;
}

void stdInsert(Item *&nod, int val)
{
    if (val < nod->val)
    {
        if (nod->left)
        {
            stdInsert(nod->left, val);
        }
        else
        {
            singleInsert(nod->left, val, nod);
        }
    }
    else
    {
        if (nod->right)
        {
            stdInsert(nod->right, val);
        }
        else
        {
            singleInsert(nod->right, val, nod);
        }
    }

    balNode(nod);
}

//
// Functii deletie
//
/*
void deleteNode(Item *&nod, int val)
{
    if (nod->val == val)
    {
        int ok = 1;

        if (nod->left)
        {
            ok = 0;

            Item *next = nod->left;
            while (next->right)
                next = next->right;

            nod->val = nod->val ^ next->val ^ (next->val = nod->val);
            deleteNode(nod->left, val);
        }

        if (ok && nod->right)
        {
            ok = 0;

            Item *next = nod->right;
            while (next->left)
                next = next->left;

            nod->val = nod->val ^ next->val ^ (next->val = nod->val);
            deleteNode(nod->right, val);
        }
    }
    else
    {
        if (nod->val > val)
        {
            if (nod->left)
                deleteNode(nod->left, val);
            else
                cout << "no such node!\n";
        }
        else
        {
            if (nod->right)
                deleteNode(nod->right, val);
            else
                cout << "no such node!\n";
        }
    }

    if (nod->left && nod->left->val == val && nod->left->left == NULL && nod->left->right == NULL)
    {
        nod->left = NULL;
    }
    else if (nod->right && nod->right->val == val && nod->right->left == NULL && nod->right->right == NULL)
    {
        nod->right = NULL;
    }

    setHeight(nod);
    balNode(nod);
}
*/

//
// Functii citire
//
/*
void readInordine(Item *nod, int indent)
{
    if (nod->left)
        readInordine(nod->left, indent + 1);

    for (int i = 0; i < indent; i++)
        cout << "\t";
    cout << "->[" << nod->height << "] " << nod->val << "\n";

    if (nod->right)
        readInordine(nod->right, indent + 1);
}
*/

void readInordineDet(Item *nod)
{
    if (nod->left)
        readInordineDet(nod->left);

    fout << nod->val << " ";

    if (nod->right)
        readInordineDet(nod->right);
}

//
// Main
//
int main()
{
    Item *root = NULL;
    int n, x;

    fin >> n >> x;
    singleInsert(root, x, NULL);

    --n;

    while (n)
    {
        fin >> x;

        stdInsert(root, x);
        --n;
    }

    readInordineDet(root);

    return 0;
}