#include <cstdlib>
#include <ctime>
#include <fstream>
#define N_MAX 500000
int N;
int v[N_MAX];

template<typename T>
inline void swap(T& x, T& y) {
    T z = x;
    x = y;
    y = z;
}

inline void read() {
    std::ifstream fin("algsort.in");

    fin >> N;
    for (int i = 0; i < N; ++i) {
        fin >> v[i];
    }

    fin.close();
}

inline int partition(int begin, int end) {
    int piv = begin + rand() % (end - begin);

    int i = begin, j = end - 1;
    while (i < j) {
        while (v[i] < v[piv]) {
            ++i;
        }
        while (v[piv] < v[j]) {
            --j;
        }

        if (i < j) {
            swap(v[i], v[j]);

            if (piv == i) {
                piv = j;
            } else
            if (piv == j) {
                piv = i;
            }

            ++i;
            --j;
        }
    }

    if (i != end && v[i] < v[piv]) {
        ++i;
    }
    
    if (i == begin) {
        swap(v[i], v[piv]);
        ++i;
    } else
    if (i == end) {
        --i;
        swap(v[i], v[piv]);
    }

    return i;
}

void quicksort(int begin, int end) {
    if (begin + 1 == end) {
        return;
    }

    int firstPartEnd = partition(begin, end);
    quicksort(begin, firstPartEnd);
    quicksort(firstPartEnd, end);
}

inline void print() {
    std::ofstream fout("algsort.out");

    fout << v[0];
    for (int i = 1; i < N; ++i) {
        fout << ' ' << v[i];
    }
    fout << '\n';

    fout.close();
}

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

    read();
    quicksort(0, N);
    print();

    return 0;
}