#include <bits/stdc++.h>


using namespace std;


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

const int NMAX = 3000002;

int k; int n;

int v[NMAX];

void quick(int st, int dr) {

	if(st >= dr)
		return ;

	int p = st + rand() % (dr - st + 1);

	swap(v[dr], v[p]);

	int index = st - 1;

	//intre st si index elemente mai mici decat pivotul v[dr] inclusiv
	//intre index + 1 si dr elemente mai mare sau egale ca pivotul

	for(int i = st; i < dr ; ++i) {
		if(v[i] < v[dr]) {
			index++;
			swap(v[i], v[index]);
			continue;
		}

		if(v[i] == v[dr] && rand() % (1<<10)  > (1<<9) ) {

			index++;
			swap(v[i], v[index]);
		}
	}



	swap(v[dr], v[index + 1]);



	 quick(st, index);

	 quick(index + 2, dr);

}


int main() {

	srand(time(NULL));

	ios_base::sync_with_stdio(false);
	fin.tie(NULL);
	
	fin >> n;
	for(int i = 1 ; i <= n ; ++i)
		fin >> v[i];
	
	quick(1, n);


	for(int i = 1 ; i <= n ; ++i)
		fout << v[i] << " ";
	return 0;
}