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

int part(std::vector<int> &myV, int left, int right, int pivot) {
    int val = myV[pivot];
    std::swap(myV[pivot], myV[right]);
    int ind = left;

    for (int i(left); i < right; i++) {
        if (myV[i] < val) {
            std::swap(myV[i], myV[ind]);
            ind++;
        }
    }

    std::swap(myV[right], myV[ind]);
    return ind;
}

void quicksort(std::vector<int> &myV, int left, int right) {
    if (left >= right) {
        return;
    }

    int pivot = left + (rand() % (left - right));
    int pos = part(myV, left, right, pivot);

    quicksort(myV, left, pos - 1);
    quicksort(myV, pos + 1, right);
}

int main() {
    srand(time(nullptr));

    std::ifstream fileIn("algsort.in");
    std::ofstream fileOut("algsort.out");

    std::vector<int> myV;
    int nV, aux;

    fileIn >> nV;

    for (int i(0); i < nV; i++) {
        fileIn >> aux;
        myV.push_back(aux);
    }

    quicksort(myV, 0, nV - 1);

    for (int val : myV) {
        fileOut << val << ' ';
    }

    return 0;
}