#include <iostream>
using namespace std;

void print_array(int* array, int size)
{
	for (int i=0; i<size;  i++)
		cout << array[i] << " ";

	cout << endl;
}

int partition(int* array, int low, int high)
{
	int x = array[high];
	int i, j;
	i = low - 1;
	for (j=low; j<=high-1; j++)
	{
		if (array[j] <= x)
		{
			i++;
			swap(array[i], array[j]);
		}
	}

	swap(array[i+1], array[high]);
	return i+1;
}

void quick_sort_impl(int* array, int low, int high)
{
	if (low < high)
	{
		int q = partition(array, low, high);
		quick_sort_impl(array, low, q-1);
		quick_sort_impl(array, q+1, high);
	}
}

void quick_sort(int* array, int size)
{
	quick_sort_impl(array, 0, size-1);
}

void main()
{
	int* array;
	int size;

	cin >> size;
	array = new int[size];

	for (int i=0; i<size; i++)
		array[i] = rand()%100;

	print_array(array, size);
	quick_sort(array, size);
	print_array(array, size);
}