// testarea catorva arbori de aici https://en.wikipedia.org/wiki/List_of_data_structures#Trees
#include <iostream>
#include <fstream>

#include <set>

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

using namespace std;
std::ifstream in("algsort.in");
std::ofstream out("algsort.out");
/*int maxlevel = 0;
int levelpermis;*/
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,node* parent)
    {
        if(root == nullptr)
        {
            root = new node(key,BLACK,nil,nil,parent);
            insert_case1(root);
        }
        else if( root == nil)
        {
            root = new node(key,RED,nil,nil,parent);
            insert_case1(root);
        }
        else if( key <= root->key)
            insert(key,root->left,root);
        else if( key > root->key)
            insert(key,root->right,root);

    }
    void srd(node*root)
    {
        if(root!= nil)
        {
            srd(root->left);
            out<<root->key<<" ";
            srd(root->right);
        }
    }
    void leftRotate(node* &T,node * x)
    {
        node * y = x->right;
        x->right = y->left;            //punem pe B in dreapta lui x
        if(y->left != nil)             //daca B nu e frunza
            y->left->parent = x;       //i rescriem tatal din y in x
        y->parent = x->parent;         //tatal lui y e tatal lui x
        if(x->parent == nullptr)       //daca x are tatal nullptr atunci radacina va fi y
            T = y;
        else                           //altfel facem ca tatal lui x sa pointeze spre y in loc de x
        {
            if(x == x->parent->left)
                x->parent->left = y;
            else
                x->parent->right = y;
        }
        y->left =x;                    //il facem pe x sa fie in stanga lui y
        x->parent =y;                  //si creem noul tata al lui x ca fiind y

    }
    /*
            |                     |
            y                     x
          /   \                 /   \
         x     C  - - - - - >  A     y
       /   \                       /   \
      A     B                     B     C
    */
    void rightRotate(node* &T,node* y)
    {
        node* x = y->left;
        y->left = x->right;
        if(x->right != nil)
            x->right->parent = y;
        x->parent = y->parent;
        if(y->parent == nullptr)
            T = x;
        else
        {
            if(y->parent->left == y)
                y->parent->left = x;
            else
                y->parent->right = x;
        }
        x->right = y;
        y->parent = x;
    }
    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))
        {
            leftRotate(root,n->parent);
            //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))
        {
            rightRotate(root,n->parent);
            //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 show(node* x)
    {
        if(x!= nil)
        {
            cout<<x->key<<" ";
            if (x->color == BLACK)
                cout<<"BLACK";
            else cout<< "RED";
            cout<<" si are copii pe : "<<x->left->key <<" && "<<x->right->key<<" ;";
            show(x->left);
            show(x->right);
        }
    }
    void insert_case5(node *n)
    {
        node *g = grandparent(n);

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

        if (n == n->parent->left)
            //rotate_right(g);
            rightRotate(root,g);
        else
            //rotate_left(g);
            leftRotate(root,g);
    }
    void insert(int x)
    {
        insert(x,root,nullptr);
        //cout<<" nodurile si culorile lor\n";
        //show(root);
        //cout<<"\ngata o colorare\n";
    }
    void showSorted()
    {
        srd(root);
    }
};
RBT rbt;
int main()
{

    //BST bst;
    //AVL avl;
    //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
}