#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <random>
#define in  fin
#define out fout

using namespace std;

ifstream fin("algsort.in");
ofstream fout("algsort.out");

struct Node{
    int val, prio;
    Node* stanga = nullptr;
    Node* dreapta = nullptr;
};

Node* root;

pair< Node*, Node* > split(Node* nod, int val_dupa_care_split){
    if(nod == nullptr) return {nullptr, nullptr};

    if(nod->val <= val_dupa_care_split){
        auto [mid, dreapta] = split(nod->dreapta, val_dupa_care_split);
        nod->dreapta = mid;
        return {nod, dreapta};
    }else{
        auto [stanga, mid] = split(nod->stanga, val_dupa_care_split);
        nod->stanga = mid;
        return {stanga, nod};
    }
}

Node* join(Node* stanga, Node* dreapta){
    if(stanga == nullptr) return dreapta;
    if(dreapta == nullptr) return stanga;

    if(stanga->prio > dreapta->prio){
        /// atunci lowkey ala din stanga devine root si ala din dreapta e merge la alea
        stanga->dreapta = join(stanga->dreapta, dreapta);
        return stanga;
    }else{
        /// atunci lowkey ii simetric numa invers
        dreapta->stanga = join(stanga, dreapta->stanga);
        return dreapta;
    }
}

Node* insert(Node* root, int val){
    auto [stanga, dreapta] = split(root, val);
    Node* nod_pt_ala_nou = new Node{val, rand()};
    return join( stanga, join(nod_pt_ala_nou, dreapta) );
}

void print_calumea(Node* root){
    if(root == nullptr) return;
    print_calumea(root->stanga);
    out << root->val << " ";
    print_calumea(root->dreapta);
}

signed main(){
    ios_base::sync_with_stdio(false);
    in.tie(NULL);

    root = nullptr;
    int n; in >> n;
    for(int i = 0; i < n; i++){
        int x; in >> x;
        root = insert(root, x);
    }

    print_calumea(root);

    return 0;
}