#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;
    }
};


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



int main(){
    ifstream in("algsort.in");
    ofstream out("algsort.out");
    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(v[j].big){
                    j=v[j].big;
                }else{
                    v[j].big=v.size();
                    v.push_back(nod(t));
                    go=false;
                }
            }
        }
    }
    //vectorul sortat:
    sorted.clear();
    desfa_arbore(sorted,v);

    for(int i=0;i<n;i++){
        out<<sorted[i]<<' ';
    }
}