#include <bits/stdc++.h>
using namespace std;

fstream in ( "algsort.in" , ios::in  );
fstream out( "algsort.out", ios::out );

struct T {
    T *pn, *ln, *rn;
    bool col; int key;
    
    T():
        pn(NULL), ln(NULL), rn(NULL), col(false), key(-1) {}

    T( T *_pn, T *_ln, T *_rn, bool _col, int _key ):
        pn(_pn), ln(_ln), rn(_rn), col(true), key(_key) {}
} *rot, *nil;

T* gnd( T *tn ) {
    if( tn != nil || tn -> pn != nil )
        return tn -> pn -> pn;
    else
        return nil;
}

T* und( T *tn ) {
    T *an = gnd( tn );
    
    if( an == nil )
        return nil;
    
    if( tn -> pn == an -> ln )
        return an -> rn;
    else
        return an -> ln;
}

void rle( T *tn ) {
    T *an = tn -> rn;
    
    if( tn -> pn != nil ) {
        if( tn == tn -> pn -> ln )
            tn -> pn -> ln = an;
        else
            tn -> pn -> rn = an;
    }
    
    if( an -> ln != nil )
        an -> ln -> pn = tn;
    an -> pn = tn -> pn; tn -> pn = an;
    
    tn -> rn = an -> ln;
    an -> ln = tn; tn = an;
    return;
}

void rri( T *tn ) {
    T *an = tn -> ln;
    
    if( tn -> pn != nil ) {
        if( tn == tn -> pn -> ln )
            tn -> pn -> ln = an;
        else
            tn -> pn -> rn = an;
    }
    
    if( an -> rn != nil )
        an -> rn -> pn = tn;
    
    an -> pn = tn -> pn;
    tn -> pn = an;
    
    tn -> ln = an -> rn;
    an -> rn = tn; tn = an;
    return;
}

void ins( T *&tn, int key ) {
    T *gn, *un;
    
    if( tn == nil )
        tn = new T( nil, nil, nil, true, key );
    else {
        while( true ) {
            if( key < tn -> key ) {
                if( tn -> ln == nil ) {
                    tn -> ln = new T( tn, nil, nil, true, key );
                    tn = tn -> ln; break;
                }
                else
                    tn = tn -> ln;
            }
            else {
                if( tn -> rn == nil ) {
                    tn -> rn = new T( tn, nil, nil, true, key );
                    tn = tn -> rn; break;
                }
                else
                    tn = tn -> rn;
            }
        }
    }
    
    while( true ) {
        if( tn -> pn == nil ) {
            tn -> col = false;
            break;
        }
        
        if( tn -> pn -> col == false )
            break;
        
        gn = gnd( tn ); un = und( tn );
        if( un -> col == true ) {
            tn -> pn -> col = false;
            gn -> col = true; un -> col = false;
            
            tn = gn;
        }
        else {
            if( tn -> pn == gn -> ln && tn == tn -> pn -> rn ) {
                rle( tn -> pn );
                tn = tn -> ln;
            }
            else
            if( tn -> pn == gn -> rn && tn == tn -> pn -> ln ) {
                rri( tn -> pn );
                tn = tn -> rn;
            }
            
            tn -> pn -> col = false;
            gn -> col = true;
            
            if( tn -> pn == gn -> rn )
                rle( gn );
            else
                rri( gn );
            break;
        }
    }
    
    while( tn -> pn != nil )
        tn = tn -> pn;
    
    return;
}

int pri( T *&tn ) {
    if( tn == nil )
        return 0;
    
    int l1 = pri( tn -> ln );
    out << tn -> key << " ";
    int l2 = pri( tn -> rn );
    
    return 1 + max( l1, l2 );
}

int main( void ) {
    ios::sync_with_stdio( false );
    rot = nil = new T;
    
    int n;
    in >> n;
    
    for( int i = 1; i <= n; i ++ ) {
        int x;
        in >> x;
        
        ins( rot, x );
    }
    
    int x = pri( rot );
    //out << endl << x;
    
    return 0;
}