#include <iostream>
#include <fstream>
#include <sstream>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <assert.h>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <set>

//#define DEBUG 1

#define for0(i,n) for (int i=0; i<n; i++)
#define iter(c) for(auto it=c.begin(); it!=c.end(); it++)
#define vec(x) vector< x >
#define pb push_back
#define ms(a,z) memset(a,z,sizeof(a));
#define mp make_pair
#define X first
#define Y second
#define sqr(x) 1LL*(x)*(x)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define all(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#ifdef int
#define read(x) scanf("%lld",&x);
#else
#define read(x) scanf("%d",&x);
#endif

#ifdef DEBUG
#define nl cout<<"\n";
#define pr(x) cout<<(x)<<" ";
#define prl(x) cout<<#x " = "<<x<<endl;
#define prp(x) cout<<"("<<(x).first<<" "<<(x).second<<") ";
#define printv(v) {for(int _=0; _<sz(v); _++) cout<<v[_]<<" "; cout<<"\n";}
#define printa(a,s) {for (int _=0; _<s; _++) cout<<a[_]<<" "; cout<<"\n";}
#define print2D(a,m,n) {for (int _=0; _<m; _++) {for (int __=0; __<n; __++) cout<<a[_][__]<<" "; cout<<"\n";} cout<<"\n";}
#define debug cout<<"ok at line "<<__LINE__<<endl;
#else
#define nl
#define pr(x)
#define prl(x)
#define prp(x)
#define printv(v)
#define printa(a,s)
#define print2D(a,m,n)
#define debug
#endif
#define MAXN 100000

using namespace std;

typedef long long ll;

const int INF = 2147483647;
const long long INFL = 9223372036854775807LL;
const double EPSILON = 0.00000001;
const long long MOD = 1000000007;

int a[2*MAXN+5];
int evens[MAXN+5], odds[MAXN+5];
int evenM[MAXN+5][20], oddM[MAXN+5][20];
vector<pair<int,int> > all_pairs;
vector<int> constr[MAXN+5];
int indegree[MAXN+5];

void preprocess(int M[MAXN+5][20], int A[MAXN], int n)
{
    for (int i=0; i<n; i++)
        M[i][0] = i;
    for (int j=1; (1<<j)<=n; j++) {
        for (int i=0; i+(1<<j)-1<n; i++) {
            if (A[M[i][j-1]] < A[M[i+(1<<(j-1))][j-1]])
                M[i][j] = M[i][j-1];
            else 
                M[i][j] = M[i+(1<<(j-1))][j-1];
        }
    }
}

int RMQ(int M[MAXN+5][20], int arr[MAXN+5], int l, int r)
{
    int k=0;
    while ((1<<k)<=(r-l+1))
        k++;
    k--;
    int ret;
    if (arr[M[l][k]] < arr[M[r-(1<<k)+1][k]])
        ret = M[l][k];
    else 
        ret = M[r-(1<<k)+1][k];
    assert(l <= ret && ret <= r);
    return ret;
}

int solve(int l, int r)
{
    list<pair<int,int>> *ret = new list<pair<int,int>>();
    if (l >= r) {
        return 0;
    }
    //pr("solve") pr(l) pr(r) nl
    if (l+1 == r) {
        all_pairs.pb(mp(a[l],a[r]));
        return sz(all_pairs)-1;
    }
    
    int id = sz(all_pairs);
    int rec1, rec2, rec3;
    if (l%2 == 0) {
        int first = RMQ(evenM, evens, l/2, r/2);
        //prl(first)
        int second = RMQ(oddM, odds, first, r/2);
        //prl(second)
        all_pairs.pb(mp(a[2*first], a[2*second+1]));
        
        rec1 = solve(l,2*first-1);
        rec2 = solve(2*first+1,2*second);
        rec3 = solve(2*second+2, r);
    }
    else {
        int first = RMQ(oddM, odds, l/2, (r-1)/2);
        //prl(first)
        int second = RMQ(evenM, evens, first+1, r/2);
        //prl(second) nl
        all_pairs.pb(mp(a[2*first+1], a[2*second]));
        
        rec1 = solve(l,2*first);
        rec2 = solve(2*first+2,2*second-1);
        rec3 = solve(2*second+1, r);
    } 

    constr[id].pb(rec1);
    constr[id].pb(rec2);
    constr[id].pb(rec3);
    indegree[rec1]++;
    indegree[rec2]++;
    indegree[rec3]++;
    return id;
}

struct item 
{
    pair<int,int> p;
    int i;
};
bool operator < (const item & a, const item & b) {
    return a.p > b.p;
}

vector<pair<int,int>> sort_pairs()
{
    int n = sz(all_pairs);
    vector<pair<int,int>> ret;
    priority_queue<item> q;
    
    for0(i,n) {
        /*prp(all_pairs[i]);
        prl(indegree[i]);
        printv(constr[i]);*/
        if (indegree[i] == 0) {
            q.push((item){all_pairs[i],i});
        }
    }
    
    while (!q.empty()) {
        item top = q.top(); q.pop();
        ret.pb(top.p);
        iter(constr[top.i]) {
            indegree[*it]--;
            if (indegree[*it] == 0) {
                q.push((item){all_pairs[*it],*it});
            }
        }
    }
    
    return ret;
}

int32_t main()
{
    #ifdef DEBUG
    freopen("C.txt","r",stdin);
    //freopen("","w",stdout);
    #endif
    
    int n;
    cin >> n;
    for0(i,n) {
        read(a[i]);
        if (i%2 == 0)
            evens[i/2] = a[i];
        else 
            odds[i/2] = a[i];
    }

    preprocess(evenM, evens, n/2);
    preprocess(oddM, odds, n/2);
    //print2D(evenM,n/2,5);
    //print2D(oddM,n/2,5);
    
    all_pairs.pb(mp(INF,INF));
    solve(0,n-1);
    vector<pair<int,int>> pair_order = sort_pairs();
    for0(i,sz(pair_order)-1) {
        printf("%d %d ",pair_order[i].first, pair_order[i].second);
    }
    printf("\n");
    return 0;
}


Measured memory_bytes: 45044