#include <iostream>
#include <fstream>
#include <stdio.h>      /* printf, scanf, puts, NULL */
#include <stdlib.h>     /* srand, rand */
#include <time.h>

using namespace std;

const int nmax = 500010;
int A[nmax], N;

int partition(int l, int r) {
    int index = rand() % (r - l) + l;
    swap(A[index], A[l]);

    /// I = A[l + 1.. i) < pivot <= A[j..r) and l < i <= j <= r
    /// A[0..l) = A0[0..l) and A[r..N) = A0[r..N) and A[l..r) is a permutation of A0[l..r)

    int i = l + 1, j = r;

    while(i < j) {
        while(i < j && A[i] < A[l]) i++;
        while(i < j && A[j - 1] >= A[l]) j--;

        // in this point (A[i] >= A[l] and A[j - 1] < A[l]) || i >= j
        if(i < j) {
            swap(A[i], A[j - 1]);
            i++;
            j--;
        }
    }
    /// i == j and A[l + 1.. i) < A[l] <= A[j..r)
    swap(A[l], A[i - 1]);
    /// post: returns k s.t. A[l..k) < A[k] <= A[k + 1.. r)
    return i - 1;
}

void Qsort(int l, int r) {
    // sorting the segment A[l..r)
    int i = l, j = r;
    while(i < j) { // checking whether the segment is not a singleton
        int k = partition(i, j);

        if(k - i <= j - k) {
            Qsort(i, k);
            i = k + 1;
        }
        else {
            Qsort(k + 1, j);
            j = k;
        }
    }
}

int main()
{
    ifstream in ("algsort.in");
    ofstream out ("algsort.out");
    in >> N;
    int i;
    for(i = 0; i < N; i++)
        in >> A[i];

    Qsort(0, N);
    for(i = 0; i < N; i++)
        out << A[i] << " ";
    return 0;
}