#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <ctime>

int a[500000];

int part(int a[], int left, int right) {

	int x = a[left];
	int i = left - 1;
	int j = right + 1;

	while (1) {

		do {

			i++;

		} while (a[i] < x);

		do {

			j--;

		} while (a[j] > x);

		if (i < j) {

			int aux = a[i];
			a[i] = a[j];
			a[j] = aux;
		}
		else {

			return j;

		}
	}
}

int random_part(int a[], int left, int right) {

	int index = rand() % (right - left) + left;

	int aux = a[index];
	a[index] = a[left];
	a[left] = aux;

	return part(a, left, right);
}

void q_sort(int a[], int left, int right) {

	if (left < right) {

		int q = random_part(a, left, right);

		q_sort(a, left, q);
		q_sort(a, q + 1, right);
	}
}

int main() {

	FILE* ip = fopen("algsort.in", "r");
	FILE* op = fopen("algsort.out", "w");

	int n;
	
	srand(time(NULL));

	fscanf(ip, "%d", &n);

	for (int i = 0; i < n; i++) {

		fscanf(ip, "%d", &a[i]);
	}

	q_sort(a, 0, n - 1);

	for (int i = 0; i < n; i++) {

		fprintf(op, "%d ", a[i]);
	}

	fclose(ip);
	fclose(op);

	return 0;
}