#include <bits/stdc++.h>
using namespace std;
#define ll long long

struct segtree{
    int size;
    vector<ll> dat;
    ll init = 1e8;

    segtree (int N) {
        size = 1;
        while (size < N) size *= 2;
        dat = vector<ll>(2*size-1, init);
    }

    ll op(ll a, ll b) {
        return min(a, b);
    }

    void update(int i, ll x) { 
        i += size-1;
        dat[i] = x;
        while (i > 0) {
            i = (i-1)/2;
            dat[i] = op(dat[2*i+1], dat[2*i+2]);
        }
        return;
    }

    ll query(int a, int b) {
        return query(a, b, 0, 0, size);
    }
    

    ll query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return init;
        if (a <= l && r <= b) return dat[k];
        ll lv, rv;
        lv = query(a, b, 2*k+1, l, (l+r)/2);
        rv = query(a, b, 2*k+2, (l+r)/2, r);
        return op(lv, rv);
    }
};

int main() {
    int N;
    cin >> N;
    vector<int> p(N+2, 0);
    vector<int> invp(N+2, 0);
    segtree st_odd(N+2), st_even(N+2);
    for (int i = 1; i <= N; i++) {
        cin >> p[i];
        invp[p[i]] = i;
        if (i%2 == 1) st_odd.update(i, p[i]);
        else st_even.update(i, p[i]);
    }
    
    set<int> used;
    used.insert(0);
    used.insert(N+1);
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<int> ans;
    
    int fl = st_odd.query(1, N+1);
    int fr = st_even.query(invp[fl]+1, N+1);
    pq.push({fl, fr});
    
    for (int z = 0; z < N/2; z++) {
        int l = pq.top().first;
        int r = pq.top().second;
        pq.pop();
        ans.push_back(l);
        ans.push_back(r);
        int l_index = invp[l], r_index = invp[r];
        auto it1 = used.lower_bound(l_index);
        auto it2 = used.lower_bound(r_index);
        it1--;
        int lside = (*it1);
        int rside = (*it2);
        if (lside < l_index-1) {
            if (lside % 2 == 0) {
                int nl = st_odd.query(lside+1, l_index);
                int nr = st_even.query(invp[nl]+1, l_index);
                pq.push({nl, nr});
            }else {
                int nl = st_even.query(lside+1, l_index);
                int nr = st_odd.query(invp[nl]+1, l_index);
                pq.push({nl, nr});
            }
        }
        if (l_index < r_index - 1) {
            if (l_index % 2 == 0) {
                int nl = st_odd.query(l_index+1, r_index);
                int nr = st_even.query(invp[nl]+1, r_index);
                pq.push({nl, nr});
            }else {
                int nl = st_even.query(l_index+1, r_index);
                int nr = st_odd.query(invp[nl]+1, r_index);
                pq.push({nl, nr});
            }
        }
        if (r_index < rside-1) {
            if (r_index % 2 == 0) {
                int nl = st_odd.query(r_index+1, rside);
                int nr = st_even.query(invp[nl]+1, rside);
                pq.push({nl, nr});
            }else {
                int nl = st_even.query(r_index+1, rside);
                int nr = st_odd.query(invp[nl]+1, rside);
                pq.push({nl, nr});
            }
        }
        
        used.insert(l_index);
        used.insert(r_index);
    }
    
    
    for (int i = 0; i < N; i++) {
        cout << ans[i];
        if (i < N-1) cout << ' ';
    }
    cout << endl;
    
    return 0;
}


Measured memory_bytes: 21744