//#include <iostream>
//#include <vector>
#include <fstream>

//#include <set>

//#include <algorithm>

#include <limits>
#include <ctime>
#include <cstdio>
#include <cstdlib>

//using namespace std;
std::ifstream in("algsort.in");
std::ofstream out("algsort.out");


class RBT
{
public:
    RBT(){init();};
    const bool RED = 1,BLACK = 0;
    struct node
    {
        int key;
        unsigned color:1;
        node* left, *right,*parent;
        node(int k,bool c, node* lt, node* rt,node* pt):key{k},color{c},left{lt},right{rt},parent{pt}{};
    };
    node *root ,* nil;
    void init()
    {
        root = nullptr;
        nil = new node(0,BLACK,nullptr,nullptr,nullptr);
    }
    node *grandparent(struct node *&n)
    {
        if ((n != nullptr) && (n->parent != nullptr))
            return n->parent->parent;
        return nullptr;
    }
    node *uncle(struct node *&n)
    {
        node *g = grandparent(n);
        if (g == nullptr)
            return nullptr; // No grandparent means no uncle
        if (n->parent == g->left)
            return g->right;
        else
            return g->left;
    }
    void insert(int key,node* &root)
    {
        if(root == nullptr)
            root = new node(key,BLACK,nil,nil,nullptr);
        else if( root == nil)
            root = new node(key,RED,nil,nil,root->parent);
        else if( key <= root->key)
            insert(key,root->left);
        else if( key > root->key)
            insert(key,root->right);
        insert_case1(root);
    }
    void srd(node* & root)
    {
        if(root!= nil)
        {
            srd(root->left);
            out<<root->key<<" ";
            srd(root->right);
        }
    }
    void rotate_left(node* &n)
    {
        node* & t = n->right;
        n->right = t->left;
        t->left = n;
        n = t;
    }
    void rotate_right(node* &n)
    {
        node* &t = n->left;
        n->left = t->right;
        t->right = n;
        n = t;
    }
    void insert_case1(node *&n) //caz radacina deci doar o coloram negru
    {
        if (n->parent == nullptr)
            n->color = BLACK;
        else
            insert_case2(n);
    }
    void insert_case2(node *&n)//caz cand
    {
        if (n->parent->color == BLACK)//avem parinte negru deci totu e ok
            return; /* Tree is still valid */
        else
            insert_case3(n);//altfel
    }
    void insert_case3(node *&n)//am epuizat cazurile cand  tatal e negru, cand tatal e rosu e problema pt ca si nodu nostru
                               //e rosu ceea ce nu e corect
                               //deacuma incolo bunicu o sa fie mereu negru, deci vedem cazurile
    {                          //cand tatal e rosu si unchiul e rosu putem colora bunicul rosu si negru pe tata si unchi

        node *u = uncle(n), *g;
        if ((u != nullptr) && (u->color == RED))//daca nu avem unchi cu culoarea rosie
        {
            n->parent->color = BLACK;           //coloram tatal
            u->color = BLACK;                   //si unchiul negru
            g = grandparent(n);
            g->color = RED;                     //bunicu rosu
            insert_case1(g);                    //si o luam de la inceput cu bunicul pt ca bunicul poate incalca iar chestii
        }
        else
            insert_case4(n);//altfel daca nu avem unchi rosu vedem alt caz
    }
    void insert_case4(node *&n) //cazul cand unchiul e negru
    {
        node *g = grandparent(n);
        if ((n == n->parent->right) && (n->parent == g->left))
        {
            rotate_left(n->parent);
            /*
            * rotate_left can be the below because of already having *g =  grandparent(n)
            *
            * struct node *saved_p=g->left, *saved_left_n=n->left;
            * g->left=n;
            * n->left=saved_p;
            * saved_p->right=saved_left_n;
            *
            * and modify the parent's nodes properly
            */

            n = n->left;
        }
        else if ((n == n->parent->left) && (n->parent == g->right))
        {
            rotate_right(n->parent);
            /*
            * rotate_right can be the below to take advantage of already having *g =  grandparent(n)
            *
            * struct node *saved_p=g->right, *saved_right_n=n->right;
            * g->right=n;
            * n->right=saved_p;
            * saved_p->left=saved_right_n;
            *
            */
            n = n->right;
        }
        insert_case5(n);
    }
    void insert_case5(node *&n)
    {
        node *g = grandparent(n);

        n->parent->color = BLACK;
        g->color = RED;

        if (n == n->parent->left)
            rotate_right(g);
        else
            rotate_left(g);
    }
    void insert(int x)
    {
        insert(x,root);
    }
    void showSorted()
    {
        srd(root);
    }
};
int main()
{


    //int x = die();
    //BST bst;
    //AVL avl;
    RBT rbt;
    //Treap treap;
    //set<int> um;

    int n,x,op,nr,nr2,j=0;
    in >> n;
    for(int i = 0  ; i< n ; i++)
    {
        //in >> op >> x;
        in >>x;
        /*switch(op)
        {
            case 1:
                treap.insert(x);
                //avl.insert(x);
                //bst.insert(x);
                  //  um.insert(x);
               break;
            case 2:
                treap.erase(x);
                //um.erase(x);
                //bst.erase(x);
                //avl.remove(x);
             break;
            case 3:
                nr = treap.find(x);
                //nr = avl.find(x);
                //nr = bst.find(x);
            //nr2 = (um.find(x)!=um.end())?1:0;
            out<<nr<<'\n';
            //ing>> nr2;
            //j++;
            //if(nr != nr2)
              //  cout<<"linia "<<j<<" "<<nr<<"!="<<nr2<<"elementul "<<x<<'\n';
            break;
        }*/
        rbt.insert(x);
        //avl.insert(x);
        //treap.insert(x);
        //bst.insert(x);
    }
    rbt.showSorted();
    //avl.showSorted();
    //treap.showSorted();
    //bst.showSorted();z
}