//#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 AVL
{
private:
    struct node
    {
        int key;
        node *left,*right;
        int height;
        node(int x, node* lt,node* rt,int h = 0):key{x},left{lt},right{rt},height{h}{};
    };
    node * root = nullptr;
    bool search(int x, node * &root)
    {
        if(root == nullptr)
            return false;
        else if(x < root->key)
            return search(x,root->left);
        else if(x > root->key)
            return search(x,root->right);
        else
            return true;
    }
    int height(node * t)
    {
        return (t == nullptr)?-1:t->height;
    }
    void insert( int x ,node* &root)
    {
        if( root == nullptr )
            root = new node{ x, nullptr, nullptr };
        else if( x < root->key )
            insert( x, root->left );
        else if(root->key < x )
            insert( x, root->right );

        balance( root );
    }
    static const int ALLOWED_IMBALANCE = 1;
    void rotateWithLeftChild( node * & k2 )//right rotate
    {
        node *k1 = k2->left;
        k2->left = k1->right;
        k1->right = k2;
        k2->height = std::max( height( k2->left ), height( k2->right ) ) + 1;
        k1->height = std::max( height( k1->left ), k2->height ) + 1;
        k2 = k1;
    }
    void rotateWithRightChild(node* &k1)//left rotate
    {
        node *k2 = k1->right;
        k1->right = k2->left;
        k2->left = k1;
        k1->height = std::max(height(k1->left),height(k1->right))+1;
        k2->height = std::max(height(k2->right),k1->height)+1;
        k1 = k2;
    }
    void doubleWithLeftChild( node * & k3 )//left right rotations
    {
        rotateWithRightChild( k3->left );
        rotateWithLeftChild( k3 );
    }
    void doubleWithRightChild(node* & k3)//right left rotations
    {
        rotateWithLeftChild(k3->right);
        rotateWithRightChild(k3);
    }
    void balance( node* &root)
    {
        if( root == nullptr )
            return;

        if( height( root->left ) - height( root->right ) > ALLOWED_IMBALANCE )//left -x case
            if( height( root->left->left ) >= height( root->left->right ) )
                rotateWithLeftChild( root );//left -left case
            else
                doubleWithLeftChild( root );//left right case
        else
            if( height( root->right ) - height( root->left ) > ALLOWED_IMBALANCE )//right-x case
                if( height( root->right->right ) >= height( root->right->left ) )
                    rotateWithRightChild( root );//right right case
                else
                    doubleWithRightChild( root );//right left case

        root->height = std::max( height( root->left ), height( root->right ) ) + 1;
    }
    node * findMin(node * &root)
    {
        if(root == nullptr)
            return nullptr;
        else if(root->left == nullptr)
            return root;
        else return findMin(root->left);
    }
    void remove( int &x, node *&root)
    {
        if( root == nullptr )
            return; // Item not found; do nothing

        if( x < root->key )
            remove( x, root->left );
        else if( root->key < x )
            remove( x, root->right );
        else if( root->left != nullptr && root->right != nullptr ) // Two children
        {
            root->key = findMin( root->right )->key;
            remove( root->key, root->right );
        }
        else
        {
            node *old = root;
            root = ( root->left != nullptr ) ? root->left : root->right;
            delete old;
        }

        balance( root );
     }
     void srd(node* &root)
     {
         if(root != nullptr)
         {
             srd(root->left);
             out<<root->key<<" ";
             srd(root->right);
         }
     }
public:

     void insert(int x)
     {
         insert(x,root);
     }
     void remove(int x)
     {
         remove(x,root);
     }
     bool find(int x)
     {
         return search(x,root);
     }
     void showSorted()
     {
         srd(root);
     }
};

int main()
{


    //int x = die();
    //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;
        }*/
        avl.insert(x);
        //treap.insert(x);
        //bst.insert(x);
    }
    avl.showSorted();
    //treap.showSorted();
    //bst.showSorted();z
}