#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

template <typename T>
struct segtree{
    int n;
    T UNIT;
    vector<T> dat;
    segtree(int n_, T unit){
        UNIT = unit;
        n = 1;
        while(n < n_) n *= 2;
        dat = vector<T>(2*n);
        for(int i = 0; i < 2*n; i++) dat[i] = UNIT;
    }

    //これを変更
    T calc(T a, T b){
        T ans = min(a, b);
        return ans;
    }
    void insert(int k, T a){
        dat[k+n-1] = a;
    }
    void update_all(){
        for(int i = n-2; i >= 0; i--){
            dat[i] = calc(dat[i*2+1], dat[i*2+2]);
        }
    }
    //k番目の値(0-indexed)をaに変更
    void update(int k, T a){
        k += n-1;
        dat[k] = a;
        while(k > 0){
            k = (k-1)/2;
            dat[k] = calc(dat[k*2+1], dat[k*2+2]);
        }
    }

    //[a, b)
    //区間[a, b]へのクエリに対してはquery(a, b+1, 0, 0, segtree.n)と呼ぶこと
    T query(int a, int b, int k, int l, int r){
        if(r <= a || b <= l) return UNIT;
        if(a <= l && r <= b) return dat[k];
        else{
            T vl = query(a, b, k*2+1, l, (l+r)/2);
            T vr = query(a, b, k*2+2, (l+r)/2, r);
            return calc(vl, vr);
        }
    }
};

const int INF = 1e+8;

int p[200000];
int idx[200001];

typedef pair<int, int> P;
vector<P> ans;
set<int> st;

P query(int l, int r, segtree<int> &sgt_even, segtree<int> &sgt_odd){
    if(l > r) return P(INF, INF);
    //cout << l << ' ' << r << endl;
    if(l%2 == 0){
        int even_max = sgt_even.query(l/2, (r+1)/2, 0, 0, sgt_even.n);
        int odd_max = sgt_odd.query(idx[even_max]/2, (r+1)/2, 0, 0, sgt_odd.n);
        return P(even_max, odd_max);
    }else{
        int odd_max = sgt_odd.query(l/2, r/2, 0, 0, sgt_odd.n);
        int even_max = sgt_even.query(idx[odd_max]/2+1, r/2+1, 0, 0, sgt_even.n);
        return P(odd_max, even_max);
    }
}

void bfs(int l_, int r_, segtree<int> &sgt_even, segtree<int> &sgt_odd){
    priority_queue<P, vector<P>, greater<P>> que;
    P tmp;
    if(l_%2 == 0){
        int even_max = sgt_even.query(l_/2, (r_+1)/2, 0, 0, sgt_even.n);
        int odd_max = sgt_odd.query(idx[even_max]/2, (r_+1)/2, 0, 0, sgt_odd.n);
        que.push(P(even_max, odd_max));
    }else{
        int odd_max = sgt_odd.query(l_/2, r_/2, 0, 0, sgt_odd.n);
        int even_max = sgt_even.query(idx[odd_max]/2+1, r_/2+1, 0, 0, sgt_even.n);
        que.push(P(odd_max, even_max));
    }
    while (!que.empty()){
        P top = que.top();
        que.pop();
        if(top.first == INF) return;
        int l = idx[top.first];
        int r = idx[top.second];
        ans.push_back(top);
        st.insert(l);
        st.insert(r);
        //cout << l << ' ' << r << endl;
        auto r_ptr = st.find(r);
        r_ptr++;
        auto l_ptr = st.find(l);
        l_ptr--;

        tmp = query(l+1, r-1, sgt_even, sgt_odd);
        que.push(tmp);
        tmp = query((*l_ptr)+1, l-1, sgt_even, sgt_odd);
        que.push(tmp);
        tmp = query(r+1, (*r_ptr)-1, sgt_even, sgt_odd);
        que.push(tmp);
    }
}

int main(){
    int N;
    cin >> N;
    segtree<int> sgt_even((N+1)/2, INF);
    segtree<int> sgt_odd(N/2, INF);

    st.insert(-1);
    st.insert(N);

    for(int i = 0; i < N; i++) {
        cin >> p[i];
        idx[p[i]] = i;
        if(i%2 == 0) sgt_even.update(i/2, p[i]);
        if(i%2 == 1) sgt_odd.update(i/2, p[i]);
    }
    bfs(0, N-1, sgt_even, sgt_odd);
    for(int i = 0; i < ans.size(); i++){
        cout << ans[i].first << ' ' << ans[i].second;
        if(i != ans.size()-1) cout << ' ';
        else cout << endl;
    }
}

Measured memory_bytes: 15600