#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#define NMAX 500001

using namespace std;

int a[NMAX], n;

void read() {

	ifstream in("algsort.in");

	in >> n;
	for (int i = 1; i <= n; i++)
		in >> a[i];
	
	in.close();
}

void quicksort(int x, int y) {

	if (x < y) {

		int i = x, j = y;
		int pos = rand() % (y - x + 1) + x;

		swap(a[i], a[pos]);

		int depX = 0, depY = -1;
		while (i < j) {

			if (a[i] > a[j]) {

				swap(a[i], a[j]);
				int aux = depX;
				depX = -depY;
				depY = -aux;
			}
			i += depX;
			j += depY;
		}

		quicksort(x, i - 1);
		quicksort(i + 1, y);
	}
}

int main() {

	srand(static_cast<unsigned int>(time(NULL)));
	read();
	quicksort(1, n);

	ofstream out("algsort.out");
	for (int i = 1; i <= n; i++)
		out << a[i] << " ";
	out.close();
}