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

int parts(int *A, int l, int r, int k)
{
    int index = l;
    std::swap(A[k], A[r]);
    for(int i = l; i < r; i++)
        if(A[i] < A[r])
        {
            std::swap(A[i], A[index]);
            index++;
        }
    std::swap(A[index], A[r]);
    return index;
}

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;
}