#include <cstdio>
#include <algorithm>

using namespace std ;

const int MAXN = 500005 ;
const int MINN = 2000 ;

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

void citireSir ( int ) ;

void liviuSort ( int * , int ) ;

void liviuSort2 ( 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 ;
}

void afisareSir ( int N )
{
  for ( int i = 0 ; i < N ; ++i )
    printf ( "%d " , A [ i ] ) ;
  printf ( "\n" ) ;
  return ;
}

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 liviuSort ( int *A , int N )
{
  int Div = sqrt ( N ) , Size = N / Div , Mod = N % Div , i , Start = 0 , heapSize = 0 ;
  if ( Div < 20 )
  {
    for ( i = 0 ; i < Mod ; ++i )
    {
      sort ( A + Start , A + (Start + Size + 1) ) ;
      pPoint [ i ] = A + Start ;
      Start += Size + 1 ;
      sPoint [ i ] = A + Start ;
      heap [ ++heapSize ] = i ;
    }
    for ( ; i < Div ; ++i )
    {
      sort ( A + Start , A + ( Start + Size ) ) ;
      pPoint [ i ] = A + Start ;
      Start += Size ;
      sPoint [ i ] = A + Start ;
      heap [ ++heapSize ] = i ;
    }
  }
  else
  {
    for ( i = 0 ; i < Mod ; ++i )
    {
      liviuSort2 (  A + Start , Size + 1 ) ;
      pPoint [ i ] = A + Start ;
      Start += Size + 1 ;
      sPoint [ i ] = A + Start ;
      heap [ ++heapSize ] = i ;
    }
    for ( ; i < Div ; ++i )
    {
      liviuSort2 ( A + Start , Size ) ;
      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 )
  {
    printf ( "%d " , *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 ;
    }
  }
}

void liviuSort2 ( 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 )
  {
    sort ( A + Start , A + (Start + Size + 1) ) ;
    pPoint2 [ i ] = A + Start ;
    Start += Size + 1 ;
    sPoint2 [ i ] = A + Start ;
    heap2 [ ++heapSize ] = i ;
  }
  for ( ; i < Div ; ++i )
  {
    sort ( A + Start , A + ( Start + Size ) ) ;
    pPoint2 [ i ] = A + Start ;
    Start += Size ;
    sPoint2 [ i ] = A + Start ;
    heap2 [ ++heapSize ] = i ;
  }
  int Nod , St , min ;
  for ( i = heapSize >> 1 ; i ; --i )
  {
    Nod = i ;
    while ( true )
    {
      St = Nod << 1 , min = Nod ;
      if ( St <= heapSize && *pPoint2 [ heap2 [ min ] ] > *pPoint2 [ heap2 [ St ] ] )
	min = St ;
      ++St ;
      if ( St <= heapSize && *pPoint2 [ heap2 [ min ] ] > *pPoint2 [ heap2 [ St ] ] )
	min = St ;
      if ( Nod != min )
      {
	swap ( heap2 [ min ] , heap2 [ Nod ] ) ;
	Nod = min ;
      }
      else
	break ;
    }
  }
  for ( i = 0 ; i < N ; ++i )
  {
    B [ i ] = *pPoint2 [ heap2 [ 1 ] ] ;
    ++pPoint2 [ heap [ 1 ] ] ;
    Nod = 1 ;
    if ( pPoint2 [ heap2 [ 1 ] ] == sPoint2 [ heap2 [ 1 ] ] )
    {
      heap2 [ 1 ] = heap2 [ heapSize ] ;
      --heapSize ;
    }
    while ( true )
    {
      St = Nod << 1 , min = Nod ;
      if ( St <= heapSize && *pPoint2 [ heap2 [ min ] ] > *pPoint2 [ heap2 [ St ] ] )
	min = St ;
      ++St ;
      if ( St <= heapSize && *pPoint2 [ heap2 [ min ] ] > *pPoint2 [ heap2 [ St ] ] )
	min = St ;
      if ( Nod != min )
      {
	swap ( heap2 [ min ] , heap2 [ Nod ] ) ;
	Nod = min ;
      }
      else
	break ;
    }
  }
  for ( i = 0 ; i < N ; ++i ) A [ i ] = B [ i ] ;
}