#include <iostream>
#include <string>
#include <stack>
#include <vector>
#include <sstream>
#include <fstream>
#include <set>
#include <algorithm>
#include <map>
#include <random>       // std::default_random_engine
#include <chrono>       // std::chrono::system_clock

int part(int lo, int hi, std::vector<int>& vec)
{
	int randIndex = lo + rand() % (hi - lo + 1);
	int pivVal = vec[randIndex];

	int i = lo - 1;
	int j = hi + 1;

	while (1)
	{
		do {
			i++;
		} while (vec[i] < pivVal);

		do {
			j--;
		} while (vec[j] > pivVal);

		if (i >= j)
		{
			return j;
		}

		std::swap(vec[i], vec[j]);
	}

	return 0;
}

void qsort(int lo, int hi, std::vector<int>& vec)
{
	if (lo < hi)
	{
		int piv = part(lo, hi, vec);
		qsort(lo, piv, vec);
		qsort(piv + 1, hi, vec);
	}
}

int main()
{
	std::ifstream f("algsort.in");
	int n, num;
	std::vector<int> vec;

	f >> n;
	for (int i = 0; i < n; ++i)
	{
		f >> num; 
		vec.push_back(num);
	}

	f.close();

	qsort(0, n - 1, vec);

	std::ofstream g("algsort.out");
	for (int i = 0; i < n; ++i)
	{
		g << vec[i] << ' ';
	}
	g.close();

	return 0;
}