#include <cstdio>
#include <algorithm>

using namespace std ;

const int MAXN = 500005 ;
const int MINN = 1000 ;

int A [ MAXN ] , B [ MAXN ] ;
int *pPoint [ MINN ] ;
int *sPoint [ MINN ] ;
int heap [ MINN ] ;

void citireSir ( int ) ;

void mergeSort ( int , int ) ;

void liviuSort ( int * , int ) ;

void swap ( int &A , int &B )
{
  A ^= B ;
  B ^= A ;
  A ^= B ;
}

inline int sqrt ( int X )
{
  int St = 1 , Dr = 10000 , mid ;
  while ( Dr - St > 1 )
  {
    mid = ( St + Dr ) >> 1 ;
    if ( mid * mid > X )
      Dr = mid ;
    else
      St = mid ;
  }
  return St ;
}

int main ( )
{
  freopen ( "algsort.in" , "r" , stdin ) ;
  freopen ( "algsort.out" , "w" , stdout ) ;
  int N ;
  scanf ( "%d" , &N ) ;
  citireSir ( N ) ;
  liviuSort ( A , N ) ;
  return 0 ;
}

void citireSir ( int N )
{
  for ( int i = 0 ; i < N ; ++i )
    scanf ( "%d" , &A [ i ] ) ;
  return ;
}

void mergeSort ( int St , int Dr )
{
  if ( Dr - St < 2 )
  {
    if ( A [ St ] > A [ Dr ] )
      swap ( A [ St ] , A [ Dr ] ) ;
    return ;
  }
  int mid = ( St + Dr ) >> 1 ;
  mergeSort ( St , mid ) ;
  mergeSort ( mid + 1  , Dr ) ;
  int k = St , l = mid + 1 , m = St ;
  while ( ( k <= mid ) && ( l <= Dr ) )
    ( A [ k ] < A [ l ] ) ? ( B [ m++ ] = A [ k++ ] ) : ( B [ m++ ] = A [ l++ ] ) ;
  while ( k <= mid )
    B [ m++ ] = A [ k++ ] ;
  while ( l <= Dr ) 
    B [ m++ ] = A [ l++ ] ;
  for ( k = St ; k<= Dr ; ++k )
    A [ k ] = B [ k ] ;
  return ;
}

void liviuSort ( int *A , int N )
{
  int Div = sqrt ( N ) , Size = N / Div , Mod = N % Div , i , Start = 0 , heapSize = 0 ;
  for ( i = 0 ; i < Mod ; ++i )
  {
    if ( Div < 20 )
      sort ( A + Start , A + (Start + Size + 1) ) ;
    else
      liviuSort ( A + Start , Size ) ;
    pPoint [ i ] = A + Start ;
    Start += Size + 1 ;
    sPoint [ i ] = A + Start ;
    heap [ ++heapSize ] = i ;
  }
  for ( ; i < Div ; ++i )
  {
    if ( Div < 20 )
      sort ( A + Start , A + ( Start + Size ) ) ;
    else
      liviuSort ( A + Start , Size - 1 ) ;
    pPoint [ i ] = A + Start ;
    Start += Size ;
    sPoint [ i ] = A + Start ;
    heap [ ++heapSize ] = i ;
  }
  int Nod , St , min ;
  for ( i = heapSize >> 1 ; i ; --i )
  {
    Nod = i ;
    while ( true )
    {
      St = Nod << 1 , min = Nod ;
      if ( St <= heapSize && *pPoint [ heap [ min ] ] > *pPoint [ heap [ St ] ] )
	min = St ;
      ++St ;
      if ( St <= heapSize && *pPoint [ heap [ min ] ] > *pPoint [ heap [ St ] ] )
	min = St ;
      if ( Nod != min )
      {
	swap ( heap [ min ] , heap [ Nod ] ) ;
	Nod = min ;
      }
      else
	break ;
    }
  }
  for ( i = 0 ; i < N ; ++i )
  {
    B [ i ] = *pPoint [ heap [ 1 ] ] ;
    ++pPoint [ heap [ 1 ] ] ;
    Nod = 1 ;
    if ( pPoint [ heap [ 1 ] ] == sPoint [ heap [ 1 ] ] )
    {
      heap [ 1 ] = heap [ heapSize ] ;
      --heapSize ;
    }
    while ( true )
    {
      St = Nod << 1 , min = Nod ;
      if ( St <= heapSize && *pPoint [ heap [ min ] ] > *pPoint [ heap [ St ] ] )
	min = St ;
      ++St ;
      if ( St <= heapSize && *pPoint [ heap [ min ] ] > *pPoint [ heap [ St ] ] )
	min = St ;
      if ( Nod != min )
      {
	swap ( heap [ min ] , heap [ Nod ] ) ;
	Nod = min ;
      }
      else
	break ;
    }
  }
  for ( i = 0 ; i < N ; ++i ) A [ i ] = B [ i ] ;
}