#include "stdafx.h"



#include <stdio.h>

int A = 1009;
int B = 1013;
int M = 1046527;
int X = 0;
int random(int n) {
	X = (A * X + B) % M;
	return X % n;
}

int* Array;
void array_swap(int idx1, int idx2) {
	int tmp = Array[idx1];
	Array[idx1] = Array[idx2];
	Array[idx2] = tmp;
}

void partition(int left, int right, int &x, int &y) {
	int p = Array[left+random(right-left+1)];
	printf("partitioning segment [%i, %i] around %i\n", left+1, right+1, p);
	x = left;
	y = right;
	while (x <= y) {
		while (Array[x] < p) x++;
		while (Array[y] > p) y--;
		if (x <= y) {
			array_swap(x, y);
			x++;
			y--;
		}
	}
	printf("segment [%i, %i] partitioned around %i\n", left+1, right+1, p);
}
void sort(int left, int right) {
	printf("sorting segment [%i, %i]\n", left+1, right+1);
	if (left == right) goto _exit;
	if (left+1 == right) {
		if (Array[left] > Array[right]) array_swap(left, right);
		goto _exit;
	}
	int x, y;
	partition(left, right, x, y);
	if (left <= x) sort(left, x);
	if (right >= y) sort(y, right);
_exit:
	printf("segment  [%i, %i] sorted\n", left+1, right+1);
}

void main() {
	int n;
	scanf("%d", &n);

	Array = new int[n];
	for (int i=0;i<n; i++) scanf("%d", &Array[i]);

	sort(0, n-1);

	printf("result: ");
	for (int i=0;i<n; i++) printf("%d ", Array[i]);
}