#include <iostream>
#include <fstream>
#include <ctime>

#define NMAX 500000

const char IN[] = "algsort.in", OUT[] = "algsort.out";

using namespace std;

int N;
int v[NMAX];
bool inOrder = true;

inline void swap(int poz1, int poz2) {
	if (&v[poz1] != &v[poz2]) {
		v[poz1] = v[poz1] ^ v[poz2];
		v[poz2] = v[poz2] ^ v[poz1];
		v[poz1] = v[poz1] ^ v[poz2];
	}
}

inline void readData() {
	freopen(IN, "r", stdin);
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		scanf(" %d", &v[i]);
		if (inOrder) inOrder = (v[i] < v[i - 1]) ? 0 : 1;
	}
	fclose(stdin);
}

inline int partition(int low, int high, int pivot) {
	int pivotVal = v[pivot];
	swap(pivot, high);
	int index = low;
	for (int i = low; i < high; ++i) {
		if (v[i] < pivotVal) swap(i, index), ++index;
	}
	swap(high, index);
	return index;
}

void qsort(int low, int high) {
	if (low == high - 1) (v[low] > v[high]) ? (swap(high, low)) : void();
	if (low == high) return;
	if (low < high) {
		int m = low + rand() % (high - low);
		int index = partition(low, high, m);
		qsort(low, index - 1);
		qsort(index + 1, high);
	}
}

int main() {
	readData();
	srand(time(NULL));
	if (!inOrder) qsort(0, N - 1);
	freopen(OUT, "w", stdout);
	for (int i = 0; i < N; ++i)
		printf("%d ", v[i]);
	printf("\n");
	fclose(stdout);
	return 0;
}