#include<fstream>
#include<cstdlib>
#include<time.h>
using namespace std;
ifstream cin("algsort.in");
ofstream cout("algsort.out");
int n,v[500005];
int chose_index(int s,int d){
    int r[3];
    for(int i=0;i<3;++i)
        r[i]=rand()%(d-s+1)+s;
    if(v[r[0]]<=v[r[1]] && v[r[0]]<=v[r[2]])
            return (v[r[1]]<=v[r[2]]?r[1]:r[2]);
    if(v[r[1]]<=v[r[0]] && v[r[1]]<=v[r[2]])
            return (v[r[0]]<=v[r[2]]?r[0]:r[2]);
    if(v[r[2]]<=v[r[0]] && v[r[2]]<=v[r[1]])
            return (v[r[0]]<=v[r[1]]?r[0]:r[1]);
}
void quicksort(int s,int d){
    if(d-s+1<=1) return;
    int index=chose_index(s,d),pivot=v[index],i,j=s;
    swap(v[index],v[d]);
    for(i=s;i<d;i++)
        if(v[i]<pivot){
            swap(v[i],v[j]);
            ++j;
        }
    swap(v[j],v[d]);
    quicksort(s,j-1);
    quicksort(j+1,d);
}
int main(){
    srand(time(NULL));
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i];
    quicksort(1,n);
    for(int i=1;i<=n;i++)
        cout<<v[i]<<' ';
}