#include <iostream>
#include <fstream>

using namespace std;

#define Hmax 500005
#define inf 0x3f3f3f3f

int H[Hmax];
int N;

void InitHeap()
{
    for ( int i = 0; i < Hmax; ++i )
            H[i] = 0;
}

inline int top_min()
{
    return H[1];
}

inline int top_max()
{
    if ( N == 1 )
            return H[1];

    return max( H[2], H[3] );
}

inline int Father( int i )
{
    return i/2;
}



inline int log2( int key )
{
    int logValue = -1;

    while ( key ){

        logValue++;
        key >>= 1;
    }

    return logValue;
}

void push( int key )
{
    int niv, fiu, tata;

    H[ ++N ] = key;

    if ( N <= 1 )   return;

    fiu = N;
    niv = log2( N );

    if ( niv % 2 == 0 )
    {
        tata = N / 2;

        if ( key > H[tata] )
        {
            while( tata && key > H[tata] )
            {
                H[fiu] = H[tata];
                fiu = tata;
                tata = fiu / 4;
                H[fiu] = key;
            }
        }
        else
        {
            tata = fiu / 4;

            while( tata && key < H[tata] )
            {
                H[fiu] = H[tata];
                fiu = tata;
                tata = fiu / 4;
                H[fiu] = key;
            }
        }
    }
    else
    {
        tata = N / 2;

        if ( key < H[tata] )
        {
            while( tata && key < H[tata] )
            {
                H[fiu] = H[tata];
                fiu = tata;
                tata = fiu / 4;
                H[fiu] = key;
            }
        }
        else
        {
            tata = fiu / 4;

            while( tata && key > H[tata] )
            {
                H[fiu] = H[tata];
                fiu = tata;
                tata = fiu / 4;
                H[fiu] = key;
            }
        }
    }
}

int MinNepot( int poz )
{
    int Sfiu = 2*poz, Rfiu = 2*poz+1;
    int minim = inf, pozitie = 0;

    if ( Sfiu <= N )
    {
        int f1 = 2*Sfiu, f2 = 2*Sfiu+1;

        if ( f1 <= N && H[f1] < minim )
                minim = H[f1],
                pozitie = f1;

        if ( f2 <= N && H[f2] < minim )
                minim = H[f2],
                pozitie = f2;
    }

    if ( Rfiu <= N )
    {
        int f1 = 2*Rfiu, f2 = 2*Rfiu+1;

        if ( f1 <= N && H[f1] < minim )
                minim = H[f1],
                pozitie = f1;

        if ( f2 <= N && H[f2] < minim )
                minim = H[f2],
                pozitie = f2;
    }

    return pozitie;
}

int MaxNepot( int poz )
{
    int Sfiu = 2*poz, Rfiu = 2*poz+1;
    int minim = -inf, pozitie = 0;

    if ( Sfiu <= N )
    {
        int f1 = 2*Sfiu, f2 = 2*Sfiu+1;

        if ( f1 <= N && H[f1] > minim )
                minim = H[f1],
                pozitie = f1;

        if ( f2 <= N && H[f2] > minim )
                minim = H[f2],
                pozitie = f2;
    }

    if ( Rfiu <= N )
    {
        int f1 = 2*Rfiu, f2 = 2*Rfiu+1;

        if ( f1 <= N && H[f1] > minim )
                minim = H[f1],
                pozitie = f1;

        if ( f2 <= N && H[f2] > minim )
                minim = H[f2],
                pozitie = f2;
    }

    return pozitie;
}

int MinFiu( int poz )
{
    int Sfiu = 2*poz, Rfiu = 2*poz+1;
    int minim = inf, pozitie = Hmax+1;

    if ( Sfiu <= N && H[Sfiu] < minim )
            minim = H[Sfiu],
            pozitie = Sfiu;

    if ( Rfiu <= N && H[Rfiu] < minim )
            minim = H[Rfiu],
            pozitie = Rfiu;

    return pozitie;
}

int MaxFiu( int poz )
{
    int Sfiu = 2*poz, Rfiu = 2*poz+1;
    int minim = -inf, pozitie = Hmax+1;

    if ( Sfiu <= N && H[Sfiu] > minim )
            minim = H[Sfiu],
            pozitie = Sfiu;

    if ( Rfiu <= N && H[Rfiu] > minim )
            minim = H[Rfiu],
            pozitie = Rfiu;

    return pozitie;
}

void pop_min()
{
    int poz = 1, x, gata = 0, v = H[ N-- ];

    while( !gata && 4*poz <= N )
    {
        x = MinNepot( poz );

        if ( v < H[x] )
                gata = 1;
        else
        {
            H[poz] = H[x];
            poz = x;
        }
    }

    H[poz] = v;
    x = MinFiu(poz);

    if ( x <= N )
            if ( v > H[x] )
            {
                H[poz] = H[x];
                H[x] = v;
            }
}

void pop_max()
{
    int poz = 2, x, gata = 0;

    if ( N == 1 )
    {
        N = 0;
        return;
    }

    if ( N > 2 && H[3] > H[2] )
            poz = 3;

    int v = H[ N-- ];

    while( !gata && 4*poz <= N )
    {
        x = MaxNepot( poz );

        if ( v > H[x] )
                gata = 1;
        else
        {
            H[poz] = H[x];
            poz = x;
        }
    }

    H[poz] = v;
    x = MaxFiu( poz );

    if ( x <= N )
            if ( v < H[x] )
            {
                H[poz] = H[x];
                H[x] = v;
            }
}

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

    int n = 0;

    f >> n;
    for ( int i = 1, a; i <= n; i++ )
            f >> a,
            push( a );

    for ( int i = 1; i <= n; i++ )
            g << H[1] << " ",
            pop_min();

    return 0;
}