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

pair<int, int> partition(int l, int r) {
    int index = rand() % (r - l) + l;
    int pivot = A[index];

    /// I = A[l.. i) < pivot && A[i..j) = pivot and A[k..r) >= pivot and l < i <= k <= j <= r

    int i = l, j = l, k = r;

    while(j < k) {
        while(j < k && A[k - 1] > pivot) k--;
        if(j < k) {
            swap(A[k - 1], A[j]);
            if(A[j] != pivot) {
                swap(A[j], A[i]);
                i++;
            }
            j++;
        }
    }

    return make_pair(i, j);
}

void Qsort(int l, int r) {
    // sorting the segment A[l..r)
    if( l + 1 < r) { // checking whether the segment is not a singleton
        pair<int, int> k = partition(l, r);
        if(k.first - l < r - k.second) {
            Qsort(l, k.first);
            Qsort(k.second, r);
        }
        else {
            Qsort(k.second, r);
            Qsort(l, k.first);
        }
    }
}

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