#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<iomanip>
#include<set>
#include<unordered_map>
using namespace std ;

#define MAXN 200007

int n ;
int a[ MAXN ] ;
int ans[ MAXN ] ;

class Tree {
public :
    int hh[ MAXN ] ;
    pair < int , int > tr[ 5 * MAXN ] ;
    void init ( int where , int IL , int IR ) {
        if ( IL == IR ) {
            tr[ where ] = { hh[ IL ] , IL } ;
            return ;
        }
        int mid = ( IL + IR ) / 2 ;
        init ( 2 * where , IL , mid ) ;
        init ( 2 * where + 1 , mid + 1 , IR ) ;
        tr[ where ] = min ( tr[ 2 * where ] , tr[ 2 * where + 1 ] ) ;
    }
    pair < int , int > query ( int where , int IL , int IR , int CURL , int CURR ) {
        if ( CURL > CURR ) { return { MAXN , MAXN } ; }
        if ( IR < CURL || CURR < IL ) { return { MAXN , MAXN } ; }
        if ( CURL <= IL && IR <= CURR ) {
            return tr[ where ] ;
        }
        int mid = ( IL + IR ) / 2 ;
        return min ( query ( 2 * where , IL , mid , CURL , CURR ) , query ( 2 * where + 1 , mid + 1 , IR , CURL , CURR ) ) ;
    }
};

Tree w_even , w_odd ;
priority_queue < pair < pair < int , int > , pair < int , int > > > q ;

pair < int , int > proc ( int st , int en ) {
    pair < int , int > ret ;
    if ( ( st % 2 ) == 1 ) {
        ret = w_odd.query ( 1 , 1 , ( n / 2 ) , ( st + 1 ) / 2 , en / 2 ) ;
    }
    else {
        ret = w_even.query ( 1 , 1 , ( n / 2 ) , st / 2 , en / 2 ) ;
    }
    ret.first = - ret.first ;
    return ret ;
}

void input ( ) {
    scanf ( "%d" , &n ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        scanf ( "%d" , &a[ i ] ) ;
    }
}

void solve ( ) {
    for ( int i = 1 ; i <= ( n / 2 ) ; ++ i ) {
        w_odd.hh[ i ] = a[ 2 * i - 1 ] ;
        w_even.hh[ i ] = a[ 2 * i ] ;
    }
    w_odd.init ( 1 , 1 , ( n / 2 ) ) ;
    w_even.init ( 1 , 1 , ( n / 2 ) ) ;
    pair < pair < int , int > , pair < int , int > > aux ;
    aux.second = { 1 , n } ;
    aux.first = w_odd.query ( 1 , 1 , ( n / 2 ) , 1 , ( n / 2 ) ) ;
    aux.first.first = - aux.first.first ;
    q.push ( aux ) ;
    int id = 0 ;
    while ( q.empty ( ) == false ) {
        aux = q.top ( ) ;
        q.pop ( ) ;
        int st , en , divl ;
        st = aux.second.first ;
        en = aux.second.second ;
        divl = aux.first.second ;
        if ( ( st % 2 ) == 1 ) { divl = 2 * divl - 1 ; }
        else { divl = 2 * divl ; }
        ans[ ++ id ] = a[ divl ] ;

        int divr ;
        
        if ( ( st % 2 ) == 1 ) {
            divr = ( w_even.query ( 1 , 1 , ( n / 2 ) , ( divl + 1 ) / 2 , en / 2 ) ).second ;
            divr *= 2 ;
        }
        else {
            divr = ( w_odd.query ( 1 , 1 , ( n / 2 ) , ( divl / 2 ) + 1 , ( en + 1 ) / 2 ) ).second ;
            divr = divr * 2 - 1 ;
        }
        ans[ ++ id ] = a[ divr ] ;


        if ( st < divl ) {
            pair < int , int > ret = proc ( st , divl - 1 ) ;
            q.push ( { ret , { st , divl - 1 } } ) ;
        }
        if ( divl + 1 < divr ) {
            pair < int , int > ret = proc ( divl + 1 , divr - 1 ) ;
            q.push ( { ret , { divl + 1 , divr - 1 } } ) ;
        }
        if ( divr < en ) {
            pair < int , int > ret = proc ( divr + 1 , en ) ;
            q.push ( { ret , { divr + 1 , en } } ) ;
        }
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        printf ( "%d " , ans[ i ] ) ;
    }
    printf ( "\n" ) ;
}


int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    input ( ) ;
    solve ( ) ;
    return 0 ;
}


Measured memory_bytes: 20596