#include <iostream>
#include <fstream>

using namespace std;

int partition(int arr[], int left, int right);
void qsort(int arr[], int left, int right);
int* readArray(int& n, ifstream& in);
void printArray(int *arr, int n, ofstream& out);

int partition(int arr[], int left, int right) {
    int randPivotIndex = rand() % (right - left + 1) + left;
    swap(arr[randPivotIndex], arr[right]);
    int i = left, pivot = arr[right];
    for(int j = left; j <= right - 1; j++) {
        if(arr[j] < pivot) {
            swap(arr[j], arr[i]);
            i++;
        }
    }
    swap(arr[i], arr[right]);
    return i;
}

void qsort(int arr[], int left, int right) {
    if(left >= right)
        return;
    int poz = partition(arr, left, right);
    qsort(arr, left, poz - 1);
    qsort(arr, poz + 1, right);
}

int* readArray(int& n, ifstream& in) {
    in >> n;
    int* v = new int[n];
    for(int i = 0; i < n; i++) {
        in >> v[i];
    }
    return v;
}

void printArray(int *arr, int n, ofstream& out) {

    for(int i = 0; i < n; i++) {
        out << arr[i] << " ";
    }
    out << endl;
}

int main() {
    ifstream in("algsort.in");
    ofstream out("algsort.out");
    int n = 0;
    int* v = readArray(n, in);

    qsort(v, 0, n - 1);
    printArray(v, n, out);

    delete[] v;
    in.close();
    out.close();
    return 0;
}