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

using namespace std;


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

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



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

    vector<nod> v;

    int n;in>>n;v.reserve(n);
    vector<int> sorted;sorted.reserve(n);
    for(int i=0;i<n;++i){
        int t;in>>t;
        sorted.push_back(t);
    }
    //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){
                v[j].n++;
                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(sorted,v);

}