#include <cmath>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define InFile "algsort.in"
#define OutFile "algsort.out"

/*
 *
 */

using namespace std;
ifstream in;
ofstream out;
class IntroSort
{
    unsigned *v;
    unsigned size;
    inline void swap( unsigned, unsigned );
    inline unsigned medianof3( unsigned, unsigned, unsigned );
    void downheap( unsigned, unsigned );
    void make_heap( unsigned, unsigned );
    unsigned partition( unsigned, unsigned, unsigned );
public:
    IntroSort();
    ~IntroSort();
    void push( istream& );
    void output( ostream& );
    inline unsigned getsize();
    void HeapSort( unsigned, unsigned );
    void introsort( unsigned, unsigned );
    void InsertionSort( unsigned, unsigned );
};
IntroSort::IntroSort()
{size=0;  //there is no element in vector
    v=(unsigned*)malloc( sizeof( unsigned ) ); // give memory
}
IntroSort::~IntroSort()
{
    free(v); //free the memory
}
void IntroSort::push( istream& in )
{++size; // a new element is inserted
    v=(unsigned*)realloc( (void*)v, size*sizeof( unsigned ) ); // creating enough space for one more element
    in>>v[size-1]; //reading date
}
void IntroSort::output( ostream& out )
{
    for( unsigned i=0; i < size; ++i ) out<<v[i]<<' '; // outputing the array
}
inline unsigned IntroSort::getsize()
{
    return size;
}
inline void IntroSort::swap( unsigned a, unsigned b ) // exchanging 2 element v[a] and v[b]
{unsigned aux=v[a];
    v[a]=v[b];
    v[b]=aux;
}
/*              Median of three
a>b|         true        |       false
---+---------------------+----------------------
b>c| true |     false    | true         | false
---+---------------------+----------------------
a>c|  X   | true | false | true | false |  X
---+---------------------+----------------------
   |  b   |  c   |  a    |  a   |  c    |  b
*/
inline unsigned IntroSort::medianof3( unsigned a, unsigned b, unsigned c )
{
    if( v[a] > v[b] )
    {
        if( v[b] > v[c] )
          return v[b];
        else if( v[a] > v[c] )
               return v[c];
        return v[a];
    }
    else if( v[b] > v[c] )
         {
             if( v[a] > v[c] )
               return v[a];
             else return v[c];
         }
    return v[b];
}
void IntroSort::downheap( unsigned begin, unsigned end )
{
    for( unsigned root=2*begin+1; root < end; )
    {
        if( root+1 < end && v[root] < v[root+1] ) ++root;
        if( v[root] <= v[begin] ) return; // if it is heap stop
        swap( root, begin );
        begin=root;
        root=2*begin+1;
    }
}
void IntroSort::make_heap( unsigned start, unsigned end )
{
    for( unsigned begin=end/2-1; begin > start; --begin )
       downheap( begin, end );
    downheap( start, end );
}
void IntroSort::HeapSort( unsigned begin, unsigned end )
{
    make_heap( begin, end );
    for( end=end-1; end > begin; --end )
    {
        swap( begin, end );
        downheap( begin, end );
    }
    swap( begin, end );
    downheap( begin, end );
}
int main()
{int N;
 IntroSort a;
    in.open( InFile );
    in>>N;
    while( N-- )
    {
        a.push( in );
    }
    out.open( OutFile );
    a.HeapSort( 0, a.getsize() );
    a.output( out );
    return EXIT_SUCCESS;
}