#include <iostream>
#include <time.h>
#include <random>
#define MAX_N 500005
using namespace std;

int v[MAX_N];
int n;

void quicksort(int first, int last)
{
	if (first >= last)
		return;
	int pivotVal = rand() % (last - first + 1) + first;
	pivotVal = v[pivotVal];

	int pivotPos = first;
	for (int i = first; i <= last; i++)
		if (v[i] < pivotVal) {
			swap(v[i], v[pivotPos]);
			pivotPos++;
		}
	int smallestPos = pivotPos - 1;
	for (int i = pivotPos; i <= last; i++)
		if (v[i] == pivotVal) {
			swap(v[i], v[pivotPos]);
			pivotPos++;
		}

	quicksort(first, smallestPos);
	quicksort(pivotPos, last);
}

int main()
{
	srand(time(NULL));
	FILE *fin = fopen("algsort.in", "r");
	FILE *fout = fopen("algsort.out", "w");
	fscanf(fin, "%d", &n);
	for (int i = 0; i < n; i++)
		fscanf(fin, "%d", &v[i]);

	quicksort(0, n - 1);

	for (int i = 0; i < n; i++)
		fprintf(fout, "%d ", v[i]);
	fprintf(fout, "\n");
}