#include <fstream>
#include <list>
#include <vector>
#include <iostream>

using namespace std;


struct nod{
    int x;
    int small;
    int big;
    nod(int X):x(X){
        small=0;
        big=0;
    }
};
ofstream out("algsort.out");

void desfa_arbore(vector<nod>& v,int i=0){
    if(v[i].small) desfa_arbore(v,v[i].small);
    out<<v[i].x<<" ";
    if(v[i].big) desfa_arbore(v,v[i].big);
}



int main(){
    ifstream in("algsort.in");

    vector<nod> v;

    int n;in>>n;v.reserve(n);
    int sorted[500000];
    for(int i=0;i<n;++i){
        in>>sorted[i];
    }
    //randomizing
    for(int i=0;i<n/2;i++){
        swap(sorted[rand()%n],sorted[rand()%n]);
    }


    v.push_back(sorted[0]);
    //citire si formare arbore
    for(int i=1;i<n;i++){
        int t=sorted[i];
        int j=0;
        bool go=true;
        while(go){
            if(t<v[j].x){
                if(v[j].small){
                    j=v[j].small;
                }else{
                    v[j].small=v.size();
                    v.push_back(nod(t));
                    go=false;
                }
            }else if(t==v[j].x){
                if(rand()%2){
                    if(v[j].small){
                        j=v[j].small;
                    }else{
                        v[j].small=v.size();
                        v.push_back(nod(t));
                        go=false;
                    }
                }else{
                    if(v[j].big){
                        j=v[j].big;
                    }else{
                        v[j].big=v.size();
                        v.push_back(nod(t));
                        go=false;
                    }
                }
            }else{
                if(v[j].big){
                    j=v[j].big;
                }else{
                    v[j].big=v.size();
                    v.push_back(nod(t));
                    go=false;
                }
            }
        }
    }
    //vectorul sortat:
    desfa_arbore(v);

}