#include <fstream>
#include <ctime>
#include <cstdlib>
#include <utility>

int parts(int *A, int left, int right, int k)
{
    int l = left, r = right, pivot = A[k];
    while(l < r)
    {
        while(A[l] < pivot) l++;
        while(A[r] > pivot) r--;
        if(l <= r)
        {
            std::swap(A[l], A[r]);
            l++;
            r--;
        }
    }
    l--;
    return l;
}

void quiksort(int *A, int left, int right)
{
    if(left >= right) return;
    int pi = left + rand() % (right - left);
    int npi = parts(A, left, right, pi);
    quiksort(A, left, npi - 1);
    quiksort(A, npi + 1, right);
}

int main(void)
{
    std::ofstream out("algsort.out");
    std::ifstream in("algsort.in");
    int nV, *nArr;
    srand(time(NULL));
    in >> nV;
    nArr = new int[nV];
    for(int i(0); i < nV; i++)
        in >> nArr[i];
    quiksort(nArr, 0, nV - 1);
    for(int i(0); i < nV; i++)
        out << nArr[i] << ' ';
    return 0;
}