#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<int,int> P;
const LL mod=1000000007;
const LL LINF=1LL<<60;
const int INF=1<<30;


template< typename T >
struct SparseTable {
    vector< vector< T > > st;
    vector< int > lookup;

    SparseTable(const vector< T > &v) {
        int b = 0;
        while((1 << b) <= v.size()) ++b;
        st.assign(b, vector< T >(1 << b));
        for(int i = 0; i < v.size(); i++) {
            st[0][i] = v[i];
        }
        for(int i = 1; i < b; i++) {
            for(int j = 0; j + (1 << i) <= (1 << b); j++) {
                st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
            }
        }
        lookup.resize(v.size() + 1);
        for(int i = 2; i < lookup.size(); i++) {
            lookup[i] = lookup[i >> 1] + 1;
        }
    }

    inline T query(int l, int r) {
        int b = lookup[r - l];
        return min(st[b][l], st[b][r - (1 << b)]);
    }
};

int main(){
    int n;cin >> n;
    vector<P> a(n,make_pair(n+1,-1)),b(n,make_pair(n+1,-1));
    for (int i = 0; i < n; i++) {
        if(i%2){
            cin >> b[i].first;
            b[i] = make_pair(b[i].first,i);
        }
        else{
            cin >> a[i].first;
            a[i] = make_pair(a[i].first,i);
        }
    }
    SparseTable<P> st1(a),st2(b);
    vector<int> ans;
    priority_queue<pair<P,pair<P,bool>>,vector<pair<P,pair<P,bool>>>, greater<pair<P,pair<P,bool>>>> pq;
    pq.push(make_pair(make_pair(0,0),make_pair(make_pair(0,n),false)));
    while(!pq.empty()){
        auto p = pq.top();pq.pop();
        int l = p.second.first.first, r = p.second.first.second;
        if(r<=l) continue;
        bool c = p.second.second;
        if(c==0){
            P ll = st1.query(l,r);
            P rr = st2.query(ll.second+1,r);
            ans.push_back(ll.first);
            ans.push_back(rr.first);
            int li = ll.second, ri = rr.second;
            P xx = st1.query(l,li);
            P yy = st2.query(xx.second+1,li);
            pq.push(make_pair(make_pair(xx.first,yy.first),make_pair(make_pair(l,li),c)));
            xx = st2.query(li+1,ri), yy = st1.query(xx.second+1,ri);	
            pq.push(make_pair(make_pair(xx.first,yy.first),make_pair(make_pair(li+1,ri),c^1)));
            xx = st1.query(ri+1,r), yy = st2.query(xx.second+1,r);	
            pq.push(make_pair(make_pair(xx.first,yy.first),make_pair(make_pair(ri+1,r),c)));
        }
        else{
            P ll = st2.query(l,r);
            P rr = st1.query(ll.second+1,r);
            ans.push_back(ll.first);
            ans.push_back(rr.first);
            int li = ll.second, ri = rr.second;
            P xx = st2.query(l,li);
            P yy = st1.query(xx.second+1,li);
            pq.push(make_pair(make_pair(xx.first,yy.first),make_pair(make_pair(l,li),c)));
            xx = st1.query(li+1,ri), yy = st2.query(xx.second+1,ri);	
            pq.push(make_pair(make_pair(xx.first,yy.first),make_pair(make_pair(li+1,ri),c^1)));
            xx = st2.query(ri+1,r), yy = st1.query(xx.second+1,r);	
            pq.push(make_pair(make_pair(xx.first,yy.first),make_pair(make_pair(ri+1,r),c)));
        }
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i] << (i==n-1?"\n":" ");
    }
    return 0;
}


Measured memory_bytes: 82812