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

using namespace std;

#define Hmax 500005

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

struct cmp {

    bool operator() (nod &a, nod &b) {
        return a.val > b.val;
    }
};

struct NODE
{
    list<int> l;

} lista[28000];

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

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

    return lg;
}

void AlexSort( int *v, int N )
{
    int log2 = lg2( N );
    int NR = ( N % log2 == 0 ? N / log2 : N / log2 + 1 );

    vector<int> lll(N+2);
    vector<int> indici(N+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 )
    {
        //for ( int j = start + 1; j <= finish; ++j )
              //  cout << lll[j] << " ";

       // cout << "\n";

        start += log2;
        finish += log2;

        finish = min( finish, N );
    }
   // cout<<endl;

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

    /*

    for ( int i = 1; i <= NR; ++i )
    {
        for ( int j = 0; j < log2; ++j )
        {
            if ( ind > N )
                    break;

            lista[i].l.push_back ( v[ ind++ ]);
        }
    }

    for ( int i = 1; i <= NR; ++i )
    {
        lista[i].l.sort();
    }



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


    for ( int i = 1; i <= NR; i++ )
    {
        nod x;
        x.val = lista[i].l.front();
        x.ind = i;

        lista[i].l.pop_front();

        heap.push( x );
    }

    int index = 1;

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

        if ( lista[ind].l.size() > 0 )
        {
            nod x;
            x.val = lista[ind].l.front();
            x.ind = ind;

            lista[ind].l.pop_front();

            heap.push( x );
        }
    }*/
}

int main()
{
    int a[Hmax], n;

    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]<<" ";

    return 0;
}