#include <algorithm>
#include <ctime>
#include <random>
using namespace std;
template <typename T>
void QSort(int l, int r, T *arr, mt19937 &mtgen)
{
if (l == r)
return;
uniform_int_distribution<int> dist(0, r - l);
T pivot = arr[dist(mtgen) + l];
int i = l, j = r;
do
{
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j)
{
swap(arr[i], arr[j]);
i++;
j--;
}
} while (i <= j);
if (j > l)
QSort(l, j, arr, mtgen);
if (i < r)
QSort(i, r, arr, mtgen);
}
void sort(unsigned *a, int n)
{
mt19937 mtgen(time(NULL));
QSort(1, n, a, mtgen);
}