#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int MAXN = 2e5 + 7 ;
int n ;
int a[ MAXN ] , f[ MAXN ] ;
int b[ MAXN ] ;
int sr[ 18 ][ 2 ][ MAXN ] ;
int rem[ 18 ][ MAXN ] ;
void fill ( int x , int lvl ) {
rem[ lvl ][ x ] = a[ x ] ;
if ( 2 * x <= n ) { fill ( 2 * x , lvl ) ; }
if ( 2 * x + 1 <= n ) { fill ( 2 * x + 1 , lvl ) ; }
}
void revert ( int x , int lvl ) {
a[ x ] = rem[ lvl ][ x ] ;
if ( 2 * x <= n ) { revert ( 2 * x , lvl ) ; }
if ( 2 * x + 1 <= n ) { revert ( 2 * x + 1 , lvl ) ; }
}
void fill_ord ( int x , int lvl , int id ) {
int tp = 0 ;
sr[ lvl ][ id ][ tp ++ ] = a[ x ] ;
for ( int aux = 1 ; aux < 20 ; ++ aux ) {
x *= 2 ;
for ( int j = 0 ; j < ( 1 << aux ) ; ++ j ) {
if ( x + j > n ) { return ; }
sr[ lvl ][ id ][ tp ++ ] = a[ x + j ] ;
}
}
}
void rec ( int wh , int lvl ) {
if ( 2 * wh > n ) {
f[ wh ] = 0 ;
return ;
}
if ( 2 * wh + 1 <= n ) {
if ( a[ wh ] < a[ 2 * wh ] && a[ wh ] < a[ 2 * wh + 1 ] ) {
f[ wh ] = 0 ;
}
else if ( a[ 2 * wh ] < a[ wh ] && a[ 2 * wh ] < a[ 2 * wh + 1 ] ) {
f[ wh ] = 1 ;
swap ( a[ wh ] , a[ 2 * wh ] ) ;
}
else {
fill ( wh , lvl ) ;
swap ( a[ wh ] , a[ 2 * wh + 1 ] ) ;
if ( 2 * wh <= n ) { rec ( 2 * wh , lvl + 1 ) ; }
if ( 2 * wh + 1 <= n ) { rec ( 2 * wh + 1 , lvl + 1 ) ; }
fill_ord ( wh , lvl , 0 ) ;
revert ( wh , lvl ) ;
swap ( a[ wh ] , a[ 2 * wh ] ) ;
swap ( a[ wh ] , a[ 2 * wh + 1 ] ) ;
if ( 2 * wh <= n ) { rec ( 2 * wh , lvl + 1 ) ; }
if ( 2 * wh + 1 <= n ) { rec ( 2 * wh + 1 , lvl + 1 ) ; }
fill_ord ( wh , lvl , 1 ) ;
revert ( wh , lvl ) ;
bool sw = false ;
for ( int i = 1 ; i <= n ; ++ i ) {
if ( sr[ lvl ][ 0 ][ i ] != sr[ lvl ][ 1 ][ i ] ) {
if ( sr[ lvl ][ 0 ][ i ] < sr[ lvl ][ 1 ][ i ] ) {
sw = true ;
}
break ;
}
}
if ( sw == false ) {
f[ wh ] = 3 ;
swap ( a[ wh ] , a[ 2 * wh ] ) ;
swap ( a[ wh ] , a[ 2 * wh + 1 ] ) ;
}
else {
f[ wh ] = 2 ;
swap ( a[ wh ] , a[ 2 * wh + 1 ] ) ;
}
}
}
else {
if ( a[ wh ] < a[ 2 * wh ] ) {
f[ wh ] = 0 ;
}
else {
f[ wh ] = 1 ;
swap ( a[ wh ] , a[ 2 * wh ] ) ;
}
return ;
}
if ( 2 * wh <= n ) { rec ( 2 * wh , lvl + 1 ) ; }
if ( 2 * wh + 1 <= n ) { rec ( 2 * wh + 1 , lvl + 1 ) ; }
}
void solve ( ) {
cin >> n ;
for ( int i = 1 ; i <= n ; ++ i ) {
cin >> a[ i ] ;
}
rec ( 1 , 0 ) ;
for ( int i = 1 ; i <= n ; ++ i ) {
cout << a[ i ] << " " ;
}
cout << "\n" ;
}
int main ( ) {
ios_base :: sync_with_stdio ( false ) ;
cin.tie ( NULL ) ;
int t = 1 ; // cin >> t ;
while ( t -- ) { solve ( ) ; }
return 0 ;
}
