/***
 *** @Patrick @Sava
 *** @Grupa @143
 ***/

#include <bits/stdc++.h>

using namespace std;

# define pb push_back
# define mp make_pair
# define FORN( a , b , c ) for ( int a = b ; a <= c ; ++ a )
# define FORNBACK( a , b , c ) for ( int a = b ; a >= c ; -- a )

class AVLTree {
public :

    struct AVLDynamic {
        AVLDynamic *st ;
        AVLDynamic *dr ;
        int value ;

        AVLDynamic ( int k )
        {
            value = k ;
            st = NULL ;
            dr = NULL ;
        }

        AVLDynamic( )
        {
            value = 0 ;
            st = NULL ;
            dr = NULL ;
        }
    };
    AVLDynamic *Root ;
    AVLTree ( )
    {
        Root = NULL ;
    }
    int Maxim ( AVLDynamic *Node )
    {
        if ( Node == NULL ) {
            cout << "Couldn't find the maximum on an empty Tree !\n" ;
            return -1 ;
        }
        if ( Node -> dr == NULL ) {
            return Node -> value ;
        }
        else {
            return Maxim ( Node -> dr ) ;
        }
    }
    bool Cauta ( AVLDynamic *Node , int searchedvalue )
    {
        if ( Node == NULL ) {
            return false ;
        }
        if ( Node -> value > searchedvalue ) {
            return Cauta ( Node -> st , searchedvalue ) ;
        }
        else if ( Node -> value < searchedvalue ) {
            return Cauta ( Node -> dr , searchedvalue ) ;
        }
        else {
            return true ;
        }
    }
    void Sterge ( AVLDynamic *&Node , int searchedvalue )
    {
        if ( Node == NULL ) {
            cout << "The searched value is not in the Tree !\n" ;
            return ;
        }
        if ( Node -> value < searchedvalue ) {
            Sterge ( Node -> dr , searchedvalue ) ;
        }
        else if ( Node -> value > searchedvalue ) {
            Sterge ( Node -> st , searchedvalue ) ;
        }
        else {
            AVLDynamic *LeftSub = Node -> st ;
            AVLDynamic *RightSub = Node -> dr ;
            delete Node ;
            if ( RightSub == NULL ) {
                Node = LeftSub ;
                return ;
            }
            int MinimumValueFromSubTree = TakeTheMinimum( RightSub , RightSub ) ;
            AVLDynamic *NewSubTree = new AVLDynamic ( MinimumValueFromSubTree ) ;
            NewSubTree -> dr = RightSub ;
            NewSubTree -> st = LeftSub ;
            Node = NewSubTree ;
            //delete NewSubTree ;
        }
    }
    void Adauga ( AVLDynamic *& Node , int newvalue )
    {
        if ( Node == NULL ) {
            Node = new AVLDynamic ( newvalue ) ;
            return ;
        }
        if ( Node -> value > newvalue ) {
            Adauga ( Node -> st , newvalue ) ;
        }
        else {
            Adauga ( Node -> dr , newvalue ) ;
        }
    }
    void WriteInIncreasingOrder ( AVLDynamic * Node )
    {
        if ( Node == NULL ) {
            return ;
        }
        WriteInIncreasingOrder( Node -> st ) ;
        cout << Node -> value << ' ' ;
        WriteInIncreasingOrder( Node -> dr ) ;
    }
    void Sort ( AVLDynamic *Node , vector < int > &Solution )
    {
        if ( Node == NULL ) {
            return ;
        }
        Sort( Node -> st , Solution ) ;
        Solution.pb ( Node -> value ) ;
        Sort ( Node -> dr , Solution ) ;
    }
private:
    int TakeTheMinimum ( AVLDynamic *&Node , AVLDynamic *&Parent )
    {
        if ( Node == NULL ){
            cout << "The Minimum element is not found because the subtree is empty !\n" ;
            return -1 ;
        }
        if ( Node -> st != NULL ) {
            return TakeTheMinimum( Node -> st , Node ) ;
        }
        else {
            int keep = Node -> value ;
            AVLDynamic *DR = Node -> dr ;
            //delete Node ;
            Parent -> st = NULL ;
            if ( DR == NULL ) {
                Node = NULL ;
            }
            else {
                Node = DR ;
            }
            return keep ;
        }
    }
};

int main()
{
    ios :: sync_with_stdio ( false ) ;

    freopen( "algsort.in" , "r" , stdin ) ;
    freopen( "algsort.in" , "w" , stdout ) ;
    AVLTree Tree ;
    int n ;
    cin >> n ;
    FORN ( i , 1 , n ) {
        int x ;
        cin >> x ;
        Tree.Adauga( Tree.Root , x ) ;
    }
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    return 0 ;
    /*FORN ( i , 1 , 100000 ) {
        Tree.Adauga( Tree.Root , i ) ;
    }
    cout << (int)Tree.Root -> height << endl ;
    return 0 ;*/
    /*Tree.Adauga( Tree.Root , 1 ) ;
    Tree.Adauga( Tree.Root , 2 ) ;
    Tree.Adauga( Tree.Root , 1 ) ;
    Tree.Adauga( Tree.Root , 2 ) ;
    Tree.Adauga( Tree.Root , 1 ) ;
    Tree.Adauga( Tree.Root , 2 ) ;
    Tree.Adauga( Tree.Root , 1 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    Tree.Sterge( Tree.Root , 1 ) ;
    //return 0 ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    Tree.Sterge( Tree.Root , 1 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    Tree.Sterge( Tree.Root , 2 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    Tree.Sterge( Tree.Root , 1 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    Tree.Sterge( Tree.Root , 2 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    Tree.Sterge( Tree.Root , 2 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    Tree.Sterge( Tree.Root , 2 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    Tree.Sterge( Tree.Root , 1 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    Tree.Sterge( Tree.Root , 1 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    Tree.Adauga( Tree.Root , 1 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    cout << "Maximul este " << Tree.Maxim( Tree.Root ) << '\n' ;
    Tree.Adauga( Tree.Root , 3 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    cout << "Maximul este " << Tree.Maxim( Tree.Root ) << '\n' ;
    //return 0 ;
    //return 0 ;
    Tree.Adauga( Tree.Root , 2 ) ;
   // return 0 ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    cout << "Maximul este " << Tree.Maxim( Tree.Root ) << '\n' ;
    //return 0 ;
    Tree.Adauga( Tree.Root , 4 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    cout << "Maximul este " << Tree.Maxim( Tree.Root ) << '\n' ;
    Tree.Adauga( Tree.Root , 5 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    cout << "Maximul este " << Tree.Maxim( Tree.Root ) << '\n' ;
    Tree.Sterge( Tree.Root , 5 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    cout << "Maximul este " << Tree.Maxim( Tree.Root ) << '\n' ;
    Tree.Sterge( Tree.Root , 4 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    cout << "Maximul este " << Tree.Maxim( Tree.Root ) << '\n' ;
    Tree.Sterge( Tree.Root , 3 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    cout << "Maximul este " << Tree.Maxim( Tree.Root ) << '\n' ;
    Tree.Sterge( Tree.Root , 2 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    cout << "Maximul este " << Tree.Maxim( Tree.Root ) << '\n' ;
    Tree.Sterge( Tree.Root , 1 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    cout << "Maximul este " << Tree.Maxim( Tree.Root ) << '\n' ;
    Tree.Adauga( Tree.Root , 1 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    cout << "Maximul este " << Tree.Maxim( Tree.Root ) << '\n' ;
    Tree.Adauga( Tree.Root , 3 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    cout << "Maximul este " << Tree.Maxim( Tree.Root ) << '\n' ;
    //return 0 ;
    //return 0 ;
    Tree.Adauga( Tree.Root , 2 ) ;
   // return 0 ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    cout << "Maximul este " << Tree.Maxim( Tree.Root ) << '\n' ;
    //return 0 ;
    Tree.Adauga( Tree.Root , 4 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    cout << "Maximul este " << Tree.Maxim( Tree.Root ) << '\n' ;
    Tree.Adauga( Tree.Root , 5 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    cout << "Maximul este " << Tree.Maxim( Tree.Root ) << '\n' ;
    Tree.Sterge( Tree.Root , 5 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    cout << "Maximul este " << Tree.Maxim( Tree.Root ) << '\n' ;
    Tree.Sterge( Tree.Root , 4 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    cout << "Maximul este " << Tree.Maxim( Tree.Root ) << '\n' ;
    Tree.Sterge( Tree.Root , 3 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    cout << "Maximul este " << Tree.Maxim( Tree.Root ) << '\n' ;
    Tree.Sterge( Tree.Root , 2 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    cout << "Maximul este " << Tree.Maxim( Tree.Root ) << '\n' ;
    Tree.Sterge( Tree.Root , 1 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    cout << "Maximul este " << Tree.Maxim( Tree.Root ) << '\n' ;
    return 0 ;
    for ( int i = 1 ; i <= 6 ; ++ i )
        cout << Tree.Cauta( Tree.Root , i ) << '\n' ;*/
    /*AVLTree Tree ;
    Tree.Adauga ( Tree.Root , 2 ) ;
    Tree.Adauga ( Tree.Root , 1 ) ;
    Tree.Adauga ( Tree.Root , 1 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    Tree.Adauga ( Tree.Root , 5 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    Tree.Adauga ( Tree.Root , 2 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    Tree.Adauga ( Tree.Root , 2 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;
    Tree.Adauga ( Tree.Root , 1 ) ;
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    cout << endl ;*/
    /*AVLTree Tree ;
    int perm [ 10000 ] ;
    int n = 1000 ;
    FORN ( i , 1 , n ) {
        perm [ i ] = i ;
    }
    random_shuffle( perm + 1 , perm + n + 1 ) ;
    FORN ( i , 1 , n ) {
        Tree.Adauga( Tree.Root , perm [ i ] ) ;
    }
    Tree.WriteInIncreasingOrder(Tree.Root) ;
    return 0 ;
    vector < int > sol ;
    sol.clear ( ) ;
    Tree.Sort( Tree.Root , sol ) ;
    for ( int i = 0 ; i < ( int ) sol.size() ; ++ i ) {
        if ( sol [ i ] != i + 1 ) {
            cout << "bad sorting\n" ;
            exit ( 0 ) ;
        }
    }
    cout << "corect\n" ;*/
    vector < int > randm ;
    srand ( time ( NULL ) ) ;
    FORN ( i , 1 , 1000 ) {
        int x = rand ( ) % 10000 + 1 ;
        Tree.Adauga( Tree.Root , x ) ;
        if ( i % 7 == 0 ) {
            randm.pb ( x ) ;
        }
    }
    vector < int > sol ;
    sol.clear ( ) ;
    Tree.Sort( Tree.Root , sol ) ;
    for ( auto x : randm ) {
        assert ( Tree.Cauta( Tree.Root , x ) == true ) ;
        Tree.Sterge( Tree.Root , x ) ;
    }
    sol.clear() ;
    Tree.Sort( Tree.Root , sol ) ;
    for ( auto x : sol ) {
        cout << x << endl ;
    }
    return 0 ;
}