#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>      /* printf, scanf, puts, NULL */
#include <stdlib.h>     /* srand, rand */
#include <time.h>       /* time */

using namespace std;

void quick_sort(vector<int> & a, int p, int r)
{
	int q = -1;
	if(p < r)
	{
		int x = a[p];
		int i = p - 1;
		int j = r + 1;
		while(true)
		{
			do j--;
			while(a[j] > x);

			do i++;
			while(a[i] < x);

			if(i < j)
			{
				swap(a[i], a[j]);
			}
			else
			{
				q = j;
				break;
			}
		}
		quick_sort(a, p, q);
		quick_sort(a, q + 1, r);
	}
}

int main()
{
#ifdef _DEBUG
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif

	//Быстрая сортировка.
	srand (time(NULL));
	int n;
	cin >> n;
	vector<int> a(n);
	cout << "Non-sorted array:\n";
	for(int i = 0; i < n; i++)
	{
		a[i] = rand() % (int)1e9 - (int)1e4;
		cout << a[i] << endl;
	}
	cout << endl;

	quick_sort(a, 0, a.size() - 1);

	cout << "Sorted array:\n";
	for(int i = 0; i < n; i++)
	{
		cout << a[i] << endl;
	}
	return 0;
}