#include <iostream>
#include <time.h>
#include <fstream>
const std :: string programName = "algsort";
std :: ifstream f (programName + ".in");
std :: ofstream g (programName + ".out");
const int NMAX = 5E5;
void read(int[], int&);
void print(int[], int);
int partition(int[], int, int);
int chooseRandom(int[], int, int);
void quickSort(int[], int, int);
int main(void) {
    int arr[NMAX + 5];
    int N = (sizeof(arr) / sizeof(arr[0]));
    read(arr, N);
    quickSort(arr, 0, N - 1);
    print(arr, N);
    return 0x0;
}
void read(int arr[], int& N) {
    f >> N;
    for (int i = 0; i < N; ++i)
        f >> arr[i];
}
void print(int arr[], int N) {
    for (int i = 0; i < N; ++i)
        g << arr[i] << ' ';
    g << "\n";
}
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j <= high - 1; ++j)
        if (arr[j] <= pivot) {
            ++i;
            std :: swap(arr[i], arr[j]);
        }
    std :: swap(arr[i + 1], arr[high]);
    return (i + 1);
}
int chooseRandom(int arr[], int low, int high) {
    srand(time(nullptr));
    int Rpivot = low + rand() % (high - low);
    std :: swap (arr[Rpivot], arr[high]);
    return partition(arr, low, high);
}
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pIndex = chooseRandom(arr, low, high);
        quickSort(arr, low, pIndex - 1);
        quickSort(arr, pIndex + 1, high);
    }
}