#include <bits/stdc++.h>

using namespace std;
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define repd(i, a, b) for(int i = (a); i > (b); i--)
#define forRev(it, a) for(__typeof((a).rbegin()) it = (a).rbegin(); it != (a).rend(); it++)
#define ll long long
#define ld long double
#define mk make_pair
#define pb push_back
#define sz(a) (int)(a).size()
#define bc(n) __builtin_popcountll(n)

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<ii> vii;
typedef vector<iii> viii;

const int N = 200000 + 7;
const int M = 475;
const int inf = 1e9 + 7;
const long long linf = 1e18 + 7;
const double pi = acos(-1);
const double eps = 1e-7;
const bool multipleTest = 0;


int res[N];
int n, p[N], rev[N];
int k;

vii C[N][2];
int cid[N];

int fBegin[N], fEnd[N];
int id[N];

void build() {
    for (int i = 1; i <= n; ++i) {
        fBegin[i] = inf;
        fEnd[i] = -inf;
    }
    for (int i = 1; i <= n; ++i) {
        id[i] = i / M;
        fBegin[id[i]] = min(fBegin[id[i]], i);
        fEnd[id[i]] = max(fEnd[id[i]], i);
        C[id[i]][i & 1].push_back(mk(p[i], i));
    }
    k = id[n] + 1;
    for (int j = 0; j < k; ++j) {
        sort(C[j][0].begin(), C[j][0].end());
        sort(C[j][1].begin(), C[j][1].end());
    }
}

void rm(int i) {
    
    for (int rc = 0; rc < 2; ++rc) {
        for (int t = 0; t + 1 < C[id[i]][rc].size(); ++t) if (C[id[i]][rc][t].second == i){
            for (; t + 1 < C[id[i]][rc].size(); ++t)
                swap(C[id[i]][rc][t], C[id[i]][rc][t + 1]);
        }
        if (!C[id[i]][rc].empty() && C[id[i]][rc].back().second == i) {
            C[id[i]][rc].pop_back();
        }
    }
}

void merge(vii& a, vii& b) {
    vii tmp = a;
    assert(tmp.size() == a.size());
    a.clear();
    int j = 0;
    for (auto xx : tmp) {
        while (j < b.size() && b[j].first < xx.first) a.push_back(b[j++]);
        a.push_back(xx);
    }
    while (j < b.size()) a.push_back(b[j++]);
}

void fix(int u, int v) {
    
    vii ls[2];
    for (int j = 0; j < 2; ++j) {
        ls[j].clear();
        for (int i = 0; i < C[id[u]][j].size(); ++i) {
            ii xx = C[id[u]][j][i];
            if (xx.second >= u && xx.second <= v) ls[j].push_back(xx);
            else C[id[u]][j][i - ls[j].size()] = xx;
        }
        for (int t = 0; t < ls[j].size(); ++t) C[id[u]][j].pop_back();
    }
    
    merge(C[id[u]][0], ls[1]);
    merge(C[id[u]][1], ls[0]);
}

void reverseSQ(int u, int v) {
    if (u > v) return;
    if (id[u] == id[v]) {
        fix(u, v);
        return;
    }
    
    int ru = id[u] + 1;
    while (ru < id[v]) {
        cid[ru++] ^= 1;
    }
    if (u == fBegin[id[u]]) cid[id[u]] ^= 1;
    else fix(u, fEnd[id[u]]);
    
    if (v == fEnd[id[v]]) cid[id[v]] ^= 1;
    else fix(fBegin[id[v]], v);
}

set<int> st;

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", p + i);
        rev[p[i]] = i;
    }
    
    build();
    for (int i = 1; i * 2 <= n; ++i) {
        int u = -1;
        for (int j = 0; j < k; ++j) {
            if (!C[j][cid[j] ^ 1].empty()) {
                if (u == -1 || p[u] > C[j][cid[j] ^ 1][0].first) {
                    u = C[j][cid[j] ^ 1][0].second;
                }
            }
        }
        int mv = n;
        auto it = st.lower_bound(u);
        if (it != st.end()) mv = *it - 1;
        int v = -1;
        for (auto& xx : C[id[u]][cid[id[u]]]) {
            if (xx.second > u && xx.second <= mv) {
                if (v == -1 || p[v] > xx.first) v = xx.second;
            }
        }
        for (int j = id[u] + 1; j < k; ++j) {
            if (!C[j][cid[j]].empty() && fBegin[j] <= mv) {
                if (fEnd[j] <= mv) {
                    if (v == -1 || p[v] > C[j][cid[j]][0].first) {
                        v = C[j][cid[j]][0].second;
                    }
                } else {
                    for (auto& xx : C[j][cid[j]]) {
                        if (xx.second > u && xx.second <= mv) {
                            if (v == -1 || p[v] > xx.first) v = xx.second;
                        }
                    }
                }
            }
        }
        printf("%d %d ", p[u], p[v]);
        rm(u);
        rm(v);
        st.insert(u);
        st.insert(v);
        reverseSQ(u + 1, v - 1);
    }
}

void test() {
}

int main() {
#ifdef _LOCAL_
    freopen("in.txt", "r", stdin);
    //    freopen("out.txt", "w", stdout);
#endif
    int Test = 1;
    if (multipleTest) {
        cin >> Test;
    }
    for(int i = 0; i < Test; ++i) {
//        test();
        solve();
    }
    
#ifdef _LOCAL_
    cout<<"\n" << 1.0 * clock() / CLOCKS_PER_SEC <<endl;
#endif
}


Measured memory_bytes: 27136