#include <iostream>
#include <fstream>

using namespace std;

typedef int MinMaxHeap[500005];

#define inf (1<<20)

MinMaxHeap H;
int N;

int log2( int key )
{
    int val = -1;

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

    return val;
}

void UpHeapMax( int index );
void UpHeapMin( int index );

void UpHeapMax( int index )
{
    int ind = index;

    while( index/4 >= 1 && H[index/4] < H[index] )
    {
        swap( H[index/4], H[index] );
        index = index/4;
    }

    if ( ind <= 1 )
            return;

    if ( H[ind/2] > H[ind] )
    {
        swap( H[ind/2], H[ind] );
        UpHeapMin( ind/2 );
    }
}

void UpHeapMin( int index )
{
    int ind = index;

    while( index/4 >= 1 && H[index/4] > H[index] )
    {
        swap( H[index/4], H[index] );
        index = index/4;
    }

    if ( ind <= 1 )
            return;

    if ( H[ind/2] < H[ind] )
    {
        swap( H[ind/2], H[ind] );
        UpHeapMax( ind/2 );
    }
}

int mingrandchild( int ind )
{
    int minim = inf, pozitie = -1;

    for ( int i = 0; i < 3; ++i )
    {
        if ( 4*ind+i <= N && H[4*ind+i] < minim )
        {
            minim = H[4*ind+i];
            pozitie = 4*ind+i;
        }
    }

    return pozitie;
}

int min2generations( int ind )
{
    int minim = inf, pozitie = -1;

    for ( int i = 0; i < 2; i++ )
    {
        if ( 2*ind+i <= N && H[2*ind+i] < minim )
        {
            minim = H[2*ind+i];
            pozitie = 2*ind+i;
        }
    }

    for ( int i = 0; i < 4; i++ )
    {
        if ( 4*ind+i <= N && H[4*ind+i] < minim )
        {
            minim = H[4*ind+i];
            pozitie = 4*ind+i;
        }
    }

    return pozitie;
}

void DownHeapMin( int index )
{
    int m;
    int ind = index;

    while( 4*index <= N )
    {
        m = mingrandchild( index );

        if ( m == -1 )  return;

        if ( H[m] > H[index] )  return;

        swap( H[m], H[index] );

        if ( H[m] > H[m/2] )
                swap( H[m], H[m/2] );

        index = m;
    }

    if ( 2*ind <= N )
    {
        m = min2generations( ind );

        if ( H[m] > H[ind] )    return;

        swap( H[m], H[ind] );

        if ( m >= 4*ind )
                if ( H[m] < H[m/2] )
                        swap( H[m], H[m/2] );
    }
}


void push( int key )
{
    H[ ++N ] = key;

    int niv = log2( N );

    if ( niv % 2 == 0 )
            UpHeapMin( N );
    else
            UpHeapMax( N );
}

void pop_min()
{
    //H[1] = H[ N-- ];

    //DownHeapMin( 1 );

    int i, last, m, parent;

    int x = H[ N-- ];

    for ( i = 1, last = N/2; i <= last; )
    {
        m = min2generations( i );

        if ( m == -1 )
            break;

        if ( x <= H[m] )
                break;

        H[i] = H[m];

        if ( m <= 2*i+1 )
        {
            i = m;
            break;
        }

        parent = m/2;

        if ( x > H[parent] )
                swap( H[parent], x );

        i = m;
    }

    H[i] = x;
}

int main()
{
    int n = 0;

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

    f >> n;

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

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