#include <fstream>
std::ifstream cin("algsort.in");
std::ofstream cout("algsort.out");
#define maxn 500050
int v[maxn],N;

void afis(int v[],int n){
    for(int i=1;i<=n;i++)
        cout<<v[i]<<' ';
}
void citire(int v[],int &n){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i];
}

void quicksort(int v[],int st, int dr){
    if(st<dr){
        int i=st, aux;
        int rad=v[dr];
        for(int j=st;j<dr;j++)
            if(v[j]<rad){
                std::swap(v[i],v[j]);
                i+=1;
            }
        v[dr]=v[i];
        v[i]=rad;
        quicksort(v,st,i-1);
        quicksort(v,i+1,dr);
    }
}
void quicksort_medianOfThree(int v[],int st, int dr){
    if(st<dr){
        int med=(st+dr)/2;
        if(v[st]>v[med])
            std::swap(v[st],v[med]);
        if(v[st]>v[dr])
            std::swap(v[dr],v[st]);
        if(v[med]>v[dr])
            std::swap(v[dr],v[med]);
        int rad=v[med], i=st+1;
        std::swap(v[med],v[dr-1]);
        for(int j=st+1;j<dr-1;j++)
            if(v[j]<rad){
                std::swap(v[i],v[j]);
                i+=1;
            }
        std::swap(v[i],v[dr-1]);
        quicksort(v,st,i-1);
        quicksort(v,i+1,dr);
    }
}

int main()
{
    citire(v,N);
    quicksort_medianOfThree(v,1,N);
    afis(v,N);
}