#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <fstream>

using namespace std;

int v[5000000];
ifstream in("algsort.in");
ofstream out("algsort.out");

int mediana(int i,int j, int k){

if(v[i]>=v[j]&&v[i]<=v[k]||v[i]<=v[j]&&v[i]>=v[k])return i;

if(v[j]>=v[i]&&v[j]<=v[k]||v[j]<=v[i]&&v[j]>=v[k])return j;

return k;
}

int pivot(int a, int b){
int x,y,z;
srand(time(NULL));
scanf("%d %d %d",&x,&y,&z);
x%=b-a+1;
y%=b-a+1;
z%=b-a+1;

return mediana(x,y,z);


}

int partitie_lometo(int pr,int ul){
int piv=pivot(pr,ul);
int i=pr-1;
for(int j=pr;j<=ul;++j){
if(v[j]<piv){
++i;
swap(v[i],v[j]);

}


}
swap(v[i+1],v[ul]);
return (i+1);
}

void QuickSort(int primul,int ultimul){
if(primul<ultimul){
int part=partitie_lometo(primul,ultimul);

QuickSort(primul,part-1);
QuickSort(part+1,ultimul);

}




}




int main()
{int n;
in>>n;
for(int i=0;i<n;i++)in>>v[i];
QuickSort(0,n-1);
for(int i=0;i<n;i++)out<<v[i]<<' ';

    return 0;
}