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

int partition_epi(std::vector<int> &a, int low, int high) {
    int pivot = a[high];
    int left = low;
    int right = high - 1;

    while (left <= right) {
        if (a[left] <= pivot) {
            left += 1;
        } else {
            swap(a[left], a[right]);
            right -= 1;
        }
    }
    swap(a[high], a[right + 1]);
    return right + 1;
}


int partition_epi_pivot_not_placed(std::vector<int> &a, int low, int high) {
    int pivot = a[high];
    int left = low;
    int right = high - 1;

    while (left < right) {
        if (a[left] <= pivot) {
            left += 1;
        } else {
            swap(a[left], a[right]);
            right -= 1;
        }
    }
    return left;
}


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

//    int p = partition_lomuto(a, low, high);
//    int p = partition_hoarei(a, low, high);
    int p = partition_epi(a, low, high);

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

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

//    int p = partition_lomuto(a, low, high);
//    int p = partition_hoarei(a, low, high);
    int p = partition_epi_pivot_not_placed(a, low, high);

    quicksort_internal(a, low, p);
    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_internal_pivot_not_placed(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;
}