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

using namespace std;

#define Hmax 500005

struct nod
{
    unsigned int val;
    unsigned short ind;
};

struct cmp {

    bool operator() ( nod &a, nod & b ) {

        return a.val > b.val;
    }
};

int lg2( int key )
{
    int lg = -1;

    while( key )
    {
        lg++;
        key >>= 1;
    }

    return lg;
}

void AlexSort( int *v, int N )
{
    int log2;

    if ( N > 40 )
            log2 = N/64;
    else
            log2 = N/8;


    int NR = ( N % log2 == 0 ? N / log2 : N / log2 + 1 );

    vector < int > lll( N + 2 );
    vector < int > indici( NR + 2 );

    int ind = 1;

    for ( int i = 1; i <= N; ++i )
            lll[i] = v[i];

    int start = 0, finish = log2;

    for ( int i = 1; i <= NR; ++i )
    {
        sort( lll.begin() + start + 1, lll.begin() + finish + 1 );

        start += log2;
        finish += log2;

        finish = min( finish, N );

        indici[i] = 2;
    }

    start = 0, finish = log2;

    for ( int i = 1; i <= NR; ++i )
    {
        start += log2;
        finish += log2;

        finish = min( finish, N );
    }

    priority_queue < nod, vector < nod >, cmp > heap;

    for ( int i = 1; i <= N; i += log2 )
    {
        nod x;
        x.ind = ind++;
        x.val = lll[i];

        heap.push( x );
    }

    int cont = N - log2 * ( NR - 1 );
    int index = 1;

    while( !heap.empty() )
    {
        v[ index++ ] = heap.top().val;
        ind = heap.top().ind;
        heap.pop();

        if ( ind != NR )
        {
            if ( indici[ind] <= log2 )
            {
                nod x;
                x.ind = ind;
                x.val = lll[ log2 * ( ind - 1 ) + indici[ind] ];
                indici[ind]++;

                heap.push( x );
            }
        }
        else
        {
            if ( indici[ind] <= cont )
            {
                nod x;
                x.ind = ind;
                x.val = lll[ log2 * ( ind - 1 ) + indici[ ind ] ];
                indici[ind]++;

                heap.push( x );
            }
        }
    }
}

int a[Hmax], n;

int main()
{
    ifstream f("algsort.in");
    ofstream g("algsort.out");

    f >> n;

    for ( int i = 1; i <= n; i++ )
            f >> a[i];

    AlexSort( a, n );

    for ( int i = 1; i <= n; i++ )
            g << a[i] << " ";

    g.close();

    return 0;
}