#include <iostream>
#include <fstream>

using namespace std;

const int HMAX = 500005;
const unsigned long long INF = ( 1 << 31 ) - 1;

class MinMaxHeap
{
    public:

        MinMaxHeap(){ };

       ~MinMaxHeap(){ };

        void push( int );
        void pop_min( );
        void pop_max( );

        inline int top_min( );
        inline int top_max( );
        inline int size( );
        inline bool empty( );

    private:

        int H[HMAX] = { 0 };
        int N = 0;

        inline int log2( int );
        inline void swap( int &, int & );
        inline int max( int, int );

        inline int LeftSon( int );
        inline int RightSon( int );
        inline int Father( int );
        inline int GrandFather( int );
        inline int Nephew( int );

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

        int min2generations( int );
        int max2generations( int );

        void ExtractMin( );
        void ExtractMax( );
};

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

    MinMaxHeap H;

    int n;
    f >> n;

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


    for ( int i = 1; i <= n; i++ )
    {
        g << H.top_min() << " ";
        H.pop_min();
    }

    return 0;
}

inline int MinMaxHeap::log2( int key )
{
    int lg = -1;

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

    return lg;
}

inline void MinMaxHeap::swap( int &a, int &b )
{
    int t = a;
    a = b;
    b = t;
}


inline int MinMaxHeap::max( int a, int b )
{
    return ( a < b ? b : a );
}

inline int MinMaxHeap::LeftSon( int i )
{
    return ( i << 1 );
}

inline int MinMaxHeap::RightSon( int i )
{
    return ( i << 1 ) + 1;
}

inline int MinMaxHeap::Father( int i )
{
    return ( i >> 1 );
}

inline int MinMaxHeap::GrandFather( int i )
{
    return ( i >> 2 );
}

inline int MinMaxHeap::Nephew( int i )
{
    return ( i << 2 );
}

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

    while( GrandFather( index ) >= 1 && H[GrandFather(index)] > H[index])
    {
        MinMaxHeap::swap( H[GrandFather(index)], H[index] );
        index = GrandFather(index);
    }

    index = ind;

    if ( index <= 1 )   return;

    if ( H[Father(index)] < H[index] )
    {
         MinMaxHeap::swap( H[index], H[Father(index)] );
         MinMaxHeap::UpHeapMax( Father(index) );
    }
}

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

    while( GrandFather(index) >= 1 && H[GrandFather(index)] < H[index] )
    {
        MinMaxHeap::swap( H[GrandFather(index)], H[index] );
        index = GrandFather(index);
    }

    index = ind;

    if ( index <= 1 )   return;

    if ( H[Father(index)] > H[index] )
    {
        MinMaxHeap::swap( H[index], H[Father(index)] );
        MinMaxHeap::UpHeapMin( Father(index) );
    }
}

int MinMaxHeap::min2generations( int index )
{
    long long minim = INF;
    int position = -1;

    if ( LeftSon(index) <= N && H[LeftSon(index)] < minim )
            minim = H[LeftSon(index)],
            position = LeftSon(index);

    if ( RightSon(index) <= N && H[RightSon(index)] < minim )
            minim = H[RightSon(index)],
            position = RightSon(index);

    for ( int i = 0; i < 4; ++i )
    {
        if ( Nephew(index)+i <= N && H[Nephew(index)+i] < minim )
                minim = H[Nephew(index)+i],
                position = Nephew(index)+i;
    }

    return position;
}

int MinMaxHeap::max2generations( int index )
{
    long long maxim = -INF;
    int position = -1;

    if ( LeftSon(index) <= N && H[LeftSon(index)] > maxim )
            maxim = H[LeftSon(index)],
            position = LeftSon(index);

    if ( RightSon(index) <= N && H[RightSon(index)] > maxim )
            maxim = H[RightSon(index)],
            position = RightSon(index);

    for ( int i = 0; i < 4; ++i )
    {
        if ( Nephew(index)+i <= N && H[Nephew(index)+i] > maxim )
                maxim = H[Nephew(index)+i],
                position = Nephew(index)+i;
    }

    return position;
}

void MinMaxHeap::ExtractMin()
{
    int i, last, m, val = H[ N-- ];

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

        if ( m == -1 )
                break;

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

        H[i] = H[m];

        if ( m <= RightSon(i) )
        {
            i = m;
            break;
        }

        if ( val > H[Father(m)] )
                MinMaxHeap::swap( H[Father(m)], val );

        i = m;
    }

    H[i] = val;
}

void MinMaxHeap::ExtractMax()
{
    int i, m, last, val = H[ N-- ], poz = 2;

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

    for ( i = poz, last = Father(N); i <= last; )
    {
        m = max2generations(i);

        if ( m == -1 )
                break;

        if ( val >= H[m] )
                break;

        H[i] = H[m];

        if ( m <= RightSon(i) )
        {
            i = m;
            break;
        }

        if ( val < H[Father(m)] )
                MinMaxHeap::swap( H[Father(m)], val );

        i = m;
    }

    H[i] = val;
}

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

    int niv = log2( N );

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

void MinMaxHeap::pop_min()
{
    ExtractMin();
}

void MinMaxHeap::pop_max()
{
    ExtractMax();
}

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

    if ( N == 2 )
            return MinMaxHeap::max( H[1], H[2] );

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

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

inline int MinMaxHeap::size()
{
    return N;
}

inline bool MinMaxHeap::empty()
{
    return ( N == 0 );
}