#include <bits/stdc++.h>
#define debug
const int MAXN = 2e5+10 ;
const int LOG = 30 ;
using namespace std ;
int N ;
int A[MAXN] ;
int tab[MAXN][LOG] ;
int dp[MAXN][LOG*2] ;
char c ;
inline void read(int &num)
{
num = 0 ;
c = getchar() ;
for(; (c>47 && c < 58) ; c=getchar() )
num = num*10 + c-48 ;
}
inline void fill_tab()
{
for(int i = 1 ; i <= N; i++ )
{
int anc = i , idx = 0 ;
while( anc )
{
tab[i][idx] = anc ;
if( anc<<1 <= N ) tab[i][idx+20] = anc<<1 ;
anc >>= 1 ;
idx ++ ;
}
}
}
int calc_dp(int sub, int anc)
{
if(sub > N/2 ) return sub ;
int add ;
int val = A[tab[sub][anc]] ;
if( sub*2 > N ) return add = sub ;
if( sub*2+1 > N ) return add = ( A[sub*2] < val ) ? sub*2 : sub ;
if( val < min(A[sub*2], A[sub*2+1]) ) return add = sub ;
if( A[sub*2] < min(val, A[sub*2+1]) ) return add = calc_dp( sub*2, anc+1 ) ;
int a = val ;
int b = A[sub*2] ;
int c = A[sub*2+1] ;
int val_esq, val_dir ;
if( a < b )
{
val_esq = calc_dp( sub*2, anc+1 ) ;
val_dir = calc_dp( sub*2+1, anc+1 ) ;
return add = min( val_esq, val_dir ) ;
}
val_esq = calc_dp( sub*2, 0 ) ;
val_dir = calc_dp( sub*2+1, 21 ) ;
return add = ( val_esq < val_dir ) ? calc_dp( sub*2+1, anc+1 ) : calc_dp( sub*2, anc+1 ) ;
}
int main()
{
read(N) ;
for(int i = 1 ; i <= N ; i++ ) read(A[i]) ;
fill_tab() ;
memset(dp , -1, sizeof dp ) ;
for(int i = 1 ; i <= N/2 ; i++ )
{
if( i*2 + 1 > N )
{
if( i*2 > N || A[i] < A[i*2] ) continue ;
swap( A[i] , A[i*2] ) ;
continue ;
}
//Case 1
if( A[i] < min( A[i*2] , A[i*2+1] ) ) continue ;
//Case 2
if( A[i*2] < min( A[i] , A[i*2+1] ) )
{
swap( A[i] , A[i*2] ) ;
continue ;
}
//Case 3 -> A[i*2+1] < min(A[i] , A[i*2])
int a = A[i] ;
int b = A[i*2] ;
int c = A[i*2+1] ;
int val_esq, val_dir ;
if( a < b )
{
val_esq = calc_dp( i*2 , 1 ) ;
val_dir = calc_dp( i*2+1, 1 ) ;
if( val_esq > val_dir )
swap(a,b) ;
A[i*2] = a ;
A[i*2+1] = b ;
}
else if( b < a )
{
val_esq = calc_dp( i*2 , 0 ) ;
val_dir = calc_dp( i*2+1, 21 ) ;
if( val_esq > val_dir )
swap(a,b) ;
A[i*2] = b ;
A[i*2+1] = a;
}
A[i] = c ;
}
for(int i = 1 ; i <= N ; i++ ) printf("%d " , A[i] ) ;
printf("\n") ;
}
