#include<bits/stdc++.h>
#define pb           push_back
#define pii          pair<int,int>
#define vi           vector<int>
#define vii         vector<pair<int,int>>
#define mp           make_pair
#define FOR(i, n) for (int i = 0; i <  (int)(n); i++)
#define FOR1(i, n) for (int i = 1; i <= (int)(n); i++)
#define FORD0(i, n) for (int i = (int)n; i >= 0; i--)
#define FORD1(i, n) for (int i = (int)n; i >= 1; i--)
#define debug(X) { cout << #X << " = " << (X) << endl; }
#define endl '\n'
#define int long long int
using namespace std;
int n;
const int block = (int)3e5;
int inv[block];
int p[block];
//second is for odd
pair<int, int> segTree[800100];
pii pMin(pii a, pii b){
    return mp(min(a.first, b.first), min(a.second, b.second));
}
    
pii query(int s, int e, int index, int qs, int qe){
    if(qe < s || qs > e) return mp(block, block);
    if(s== e){
        return segTree[index];
    }
    if(qs <= s && e <= qe){
        return segTree[index];
    }
    int mid = (s+e)/2;
    return pMin(query(s, mid, index*2, qs, qe),
            query(mid+1,e, index*2+1, qs, qe));
}

void update(int s, int e, int index, int loc, int val = block){
    if(s == e && s == loc){
        if(s & 1)segTree[index].second = block;
        else segTree[index].first = block;
        return;
    }
    if(loc <s || loc > e) return;
    int mid = (s+e)/2;
    update(s, mid, index*2, loc, val);
    update(mid+1, e, index*2+1, loc, val);
    segTree[index] = pMin(segTree[index*2], segTree[index*2+1]);
}

void buildTree(int s, int e, int index){
    if(s == e){
        segTree[index] = mp(block, block); 
        if(s & 1)segTree[index].second = p[s];//SECOND IF FOR ODD!!!!!!!!!!!!1
        else segTree[index].first = p[s];//FIRST IS FOR EVEN!!!!!!!!!!!!!!!!!!!
        return;
    }
    int mid = (s+e)/2;
    buildTree(s, mid, index*2);
    buildTree(mid+1, e, index*2+1);
    segTree[index] = pMin(segTree[index*2], segTree[index*2+1]);
}
vii ans;
int q(int s, int e){
    pii q = query(1, n, 1, s, e);
    if(s & 1)return q.second;
    else return q.first;
}
void solve(int s, int e){
//    cout << s <<  " " << e << endl;
    //min-heap
    priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> pq;
    pii t = query(1, n, 1, 1, n-1);
    pq.push(mp(t.second, mp(1, n)));
    while(!pq.empty()){
        pair<int, pii> temp = pq.top();
        pq.pop();
        s = temp.second.first;
        e = temp.second.second;
        if(e -s < 1)continue;
        int val = temp.first;
        pii temp2 = query(1, n, 1, inv[val] + 1, e);
        int second = (e - inv[temp2.first]) % 2 == 0 ? temp2.first : temp2.second;
        ans.pb(mp(val, second));
        pq.push(mp(q(s, inv[val] - 2), mp(s, inv[val] -1)));
        pq.push(mp(q(inv[val] + 1, inv[second] - 2), mp(inv[val] + 1, inv[second] -1)));
        pq.push(mp(q(inv[second] + 1, e - 1), mp(inv[second] + 1, e)));
    }
}

signed main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    cin >> n;
    FOR1(i, n)cin >> p[i], inv[p[i]] = i;
    buildTree(1, n, 1);
    solve(1, n);
//    sort(ans.begin(), ans.end());
    for(auto x: ans)cout << x.first << " " << x.second << " ";
}




Measured memory_bytes: 24624