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

unsigned arr[114514];

inline void __REACH_SORT(const unsigned &s,const unsigned &e,const unsigned &depth,const unsigned &maxdep){
    if(e<=s+1)
        return;
    if(depth>maxdep){
        make_heap(arr+s,arr+e);
        sort_heap(arr+s,arr+e);
        return;
    }   
    mt19937 mtRnd(chrono::system_clock::now().time_since_epoch().count());
    uniform_int_distribution<> dis(s,e-1);
    const unsigned pv=arr[dis(mtRnd)];
    unsigned Ith(s),Jth(s),Kth(e);
    while(Ith<Kth){
        if(arr[Ith]<pv)
            swap(arr[Ith++],arr[Jth++]);
        else if(arr[Ith]>pv)
            swap(arr[Ith],arr[--Kth]);    
        else Ith++;
    }
    __REACH_SORT(s,Jth,depth+1,maxdep);
    __REACH_SORT(s+Kth,e-Kth,depth+1,maxdep);
}

inline void reach_sort(const unsigned &s,const unsigned &e){
    __REACH_SORT(s,e,0,floor(1.0*log2(s+e)));
}

int n;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
    reach_sort(0,n);
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    return 0;
}