#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <random>

using namespace std;

int partition_lomuto(std::vector<int> &a, int low, int high) {
    // 90 pct pt input randomizat
    int pivot = a[high];
    int read_head = low;
    int write_head = low;
    while (read_head < high) {
        if (a[read_head] <= pivot) {
            std::swap(a[read_head], a[write_head]);
            write_head += 1;
        }
        read_head += 1;
    }
    std::swap(a[write_head], a[high]);
    return write_head;
}

int partition_hoare(std::vector<int> &a, int low, int high) {
    //  100pct pt input randomizat, 60 pt nerandomizat
    int pivot = a[low];
    int i = low;
    int j = high + 1;
    while (true) {
        i += 1;
        j -= 1;
        while (i <= high && a[i] < pivot) {
            i += 1;
        }

        while (j > low && a[j] > pivot) {
            j -= 1;
        }

        if (j <= i) break;

        swap(a[i], a[j]);
    }
    swap(a[j], a[low]);

    return j;
}

void quicksort_3way_partition(std::vector<int> &a, int low, int high) {
    if (high <= low) {
        return;
    }
    int lt = 0;
    int i = 0;
    int gt = high;

    int p = a[low];
    while (i <= gt) {
        if (a[i] < p) {
            swap(a[i], a[lt]);
            lt += 1;
            i += 1;
        } else if (a[i] > p) {
            swap(a[i], a[gt]);
            gt -= 1;
        } else {
            i++;
        }
    }

    quicksort_3way_partition(a, low, lt - 1);
    quicksort_3way_partition(a, gt + 1, high);
}

void quicksort_internal(std::vector<int> &a, int low, int high) {
    if (high <= low) {
        return;
    }

    int p = partition_lomuto(a, low, high);

    quicksort_internal(a, low, p - 1);
    quicksort_internal(a, p + 1, high);
}

void quicksort(std::vector<int> &a) {
    auto low = 0;
    int high = a.size() - 1;
    auto rng = std::default_random_engine{};
    std::shuffle(std::begin(a), std::end(a), rng);
//    quicksort_internal(a, low, high);
    quicksort_3way_partition(a, low, high);
}

int main() {
    std::ifstream f("algsort.in");
    std::ofstream g("algsort.out");
    int n;
    f >> n;
    vector<int> arr(n);

    for (int i = 0; i < n; ++i) {
        int nr;
        f >> nr;
        arr[i] = nr;
    }
//    for (const int &a: arr) {
//        std::cout << a << " ";
//    }
//    std::cout << endl;
    quicksort(arr);

    for (const int &a: arr) {
//        std::cout << a << " ";
        g << a << " ";
    }


    return 0;
}