/***
 *** @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 ;
        unsigned char height ;
        int value ;

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

        AVLDynamic( )
        {
            value = 0 ;
            height = 0 ;
            st = NULL ;
            dr = NULL ;
        }
    };
    AVLDynamic *Root ;
    AVLTree ( )
    {
        Root = NULL ;
    }
    ~AVLTree ( )
    {
        exit ( 0 ) ;
        while ( Root != NULL ) {
            Sterge ( Root , Maxim ( Root ) ) ;
        }
    }
    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 ;
            Balance ( Node ) ;
        }
    }
    void Adauga ( AVLDynamic *& Node , int newvalue )
    {
        if ( Node == NULL ) {
            Node = new AVLDynamic ( newvalue ) ;
            Balance ( Node ) ;
            return ;
        }
        if ( Node -> value > newvalue ) {
            Adauga ( Node -> st , newvalue ) ;
        }
        else {
            Adauga ( Node -> dr , newvalue ) ;
        }
        Balance( Node ) ;
    }
    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 ;
        }
        WriteInIncreasingOrder( Node -> st ) ;
        Solution.pb ( Node -> value ) ;
        WriteInIncreasingOrder( Node -> dr ) ;
    }
private:
    int GetHeight ( AVLDynamic * Node )
    {
        if ( Node != NULL ) {
            return Node -> height ;
        }
        return 0 ;
    }
    int BalanceSituation ( AVLDynamic * Node )
    {
        return -GetHeight( Node -> st ) + GetHeight( Node -> dr ) ;
    }
    void FixHeight ( AVLDynamic *& Node )
    {
        if ( Node == NULL ) {
            return ;
        }
        unsigned char LeftHeight = GetHeight( Node -> st ) ;
        unsigned char RightHeight = GetHeight( Node -> dr ) ;
        Node -> height = max ( LeftHeight , RightHeight ) + 1 ;
    }
    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 {
            Parent -> st = NULL ;
            int keep = Node -> value ;
            delete Node ;
            return keep ;
        }
    }
    void Balance ( AVLDynamic *&Node )
    {
        FixHeight( Node ) ;
        if ( BalanceSituation( Node ) == 2 ) {
            if ( BalanceSituation( Node -> dr ) < 0 ) {
                RotateRight( Node -> dr ) ;
            }
            RotateLeft( Node ) ;
        }
        if ( BalanceSituation( Node ) == -2 )
        {
            if ( BalanceSituation( Node -> st ) < 0 ) {
                RotateLeft( Node -> st ) ;
            }
            RotateRight( Node ) ;
        }
    }
    void RotateRight ( AVLDynamic *&Node )
    {
        AVLDynamic *LeftSubTree = Node -> st ;
        AVLDynamic *NewNode ;
        NewNode = LeftSubTree ;
        if ( NewNode == NULL ) {
            return ;
        }
        Node -> st = NULL ;
        AVLDynamic *Keep ;
        Keep = LeftSubTree -> dr ;
        NewNode -> dr = Node ;
        if ( Keep != NULL )
            NewNode -> dr -> st = Keep ;
        else
            NewNode -> dr -> st = NULL ;
        Node = NewNode ;
        if ( Node -> dr != NULL ) {
            FixHeight( Node -> dr -> st ) ;
            FixHeight( Node -> dr -> dr ) ;
            FixHeight( Node -> dr ) ;
        }
        if ( Node -> st != NULL ) {
            FixHeight( Node -> st -> st ) ;
            FixHeight( Node -> st -> dr ) ;
            FixHeight( Node -> st ) ;
        }
        FixHeight( Node ) ;
    }
    void RotateLeft ( AVLDynamic *&Node )
    {
        AVLDynamic *RightSubTree = Node -> dr ;
        AVLDynamic *NewNode ;
        NewNode = RightSubTree ;
        if ( NewNode == NULL ) {
            return ;
        }
        Node -> dr = NULL ;
        AVLDynamic *Keep ;
        Keep = RightSubTree -> st ;
        NewNode -> st = Node ;
        if ( Keep != NULL )
            NewNode -> st -> dr = Keep ;
        else NewNode -> st -> dr = NULL ;
        Node = NewNode ;
        if ( Node -> dr != NULL ) {
            FixHeight( Node -> dr -> st ) ;
            FixHeight( Node -> dr -> dr ) ;
            FixHeight( Node -> dr ) ;
        }
        if ( Node -> st != NULL ) {
            FixHeight( Node -> st -> st ) ;
            FixHeight( Node -> st -> dr ) ;
            FixHeight( Node -> st ) ;
        }
        FixHeight( Node ) ;
    }
};

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

    freopen( "algsort.in" , "r" , stdin ) ;
    freopen( "algsort.out" , "w" , stdout ) ;
    int n ;
    cin >> n ;
    AVLTree Tree ;
    FORN ( i , 1 , n ) {
        int x ;
        cin >> x ;
        Tree.Adauga( Tree.Root , x ) ;
    }
    Tree.WriteInIncreasingOrder( Tree.Root ) ;
    /*AVLTree Tree ;
    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" ;*/
    return 0 ;
}