#include <iostream>
#include <time.h>
using namespace std;

void quickSort(int mas[], int n)
{
	int m = mas[n / 2], i = 0, j = n;
	do {
		while (mas[i] < m)
			i++;
		while (mas[j] > m)
			j--;
		if (i <= j)
		{
			int temp = mas[i];
			mas[i] = mas[j];
			mas[j] = temp;
			i++;
			j--;
		}
	} while (i <= j);

		if (i < n)
			quickSort(mas + i, n - i);
		if (j > 0)
			quickSort(mas, j);
}
int main()
{
	srand(time(NULL));
	int n;
	cin >> n;
	int* mas = new int[n];

	for (int i = 0; i < n; i++)
	{
		mas[i] = rand() % 20 + 1;
		cout << mas[i] << ' ';
	}
	cout << endl;
	quickSort(mas,n-1);

	for (int i = 0; i < n; i++)
	{
		cout << mas[i] << ' ';
	}
	system("pause");
}