#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <random>
#include <chrono>

using namespace std;

typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

const ll SIZE = 1e5 * 2 + 100, INF = 1e9 + 10, MOD = 1e9 + 7;

vector<ll> vec, cur;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

set<tuple<ll, ll, ll, ll>> cubes;
vector<tuple<ll, ll, ll, ll>> cubVec;

ll n, tree[SIZE * 4][2];
vector<ll> perm;
vector<ll> pos;
vector<bool> used;

void upd(int v, int l, int r, int pos, int val) {
    if (l == r - 1) {
        tree[v][!(l % 2)] = INF;
        tree[v][l % 2] = val;
    }
    else {
        int mid = (l + r) / 2;
        if (pos < mid) {
            upd(v * 2 + 1, l, mid, pos, val);
        }
        else {
            upd(v * 2 + 2, mid, r, pos, val);
        }
        for (int i = 0; i <= 1; i++) tree[v][i] = min(tree[v * 2 + 1][i], tree[v * 2 + 2][i]);
    }
}

pair<ll, ll> get(int v, int l, int r, int askl, int askr) {
    if (l >= askr || r <= askl) return { INF, INF };

    if (l >= askl && r <= askr) return { tree[v][0], tree[v][1] };

    int mid = (l + r) / 2;
    pair<ll, ll> q = get(v * 2 + 1, l, mid, askl, askr), q2 = get(v * 2 + 2, mid, r, askl, askr);

    return { min(q.first, q2.first), min(q.second, q2.second) };
}
void input() {
    cin >> n;
    perm.resize(n);
    used.resize(n);
    pos.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> perm[i];
        pos[perm[i] - 1] = i;
        upd(0, 0, n, i, perm[i] - 1);
    }
}

vector<ll> newPerm;

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt merged(InputIt1 first1, InputIt1 last1,
    InputIt2 first2, InputIt2 last2,
    OutputIt d_first)
{
    for (; first1 != last1; ++d_first) {
        if (first2 == last2) {
            return std::copy(first1, last1, d_first);
        }
        if (*first2 < *first1) {
            *d_first = *first2;
            ++first2;
        }
        else {
            *d_first = *first1;
            ++first1;
        }
    }
    return std::copy(first2, last2, d_first);
}

vector<ll> ans;

void sol() {
    set<tuple<ll, ll, ll>> qu;
    qu.insert({ 0, 0, n });
    while (!qu.empty()) {
        tuple<ll, ll, ll> cur = (*qu.begin());
        qu.erase(qu.begin());
        ll l = get<1>(cur), r = get<2>(cur);

        if (l == r - 2) {
            ans.push_back(perm[l]);
            ans.push_back(perm[l + 1]);
            continue;
        }
        else {
            pair<ll, ll> mn = get(0, 0, n, l, r);
            if (l % 2 != 0) swap(mn.first, mn.second);

            pair<ll, ll> q2;
            ll vl1 = pos[mn.first], vl2;
            q2 = get(0, 0, n, vl1, r);
            if (l % 2 != 0) swap(q2.first, q2.second);
            vl2 = pos[q2.second];

            mn.second = q2.second;
            ans.push_back(mn.first + 1);
            ans.push_back(mn.second + 1);

            if (vl1 != l) {
                pair<ll, ll> q = get(0, 0, n, l, vl1);
                if (l % 2 != 0) swap(q.first, q.second);
                qu.insert({ q.first, l, vl1 });
            }
            if (vl1 + 1 != vl2) {
                pair<ll, ll> q2 = get(0, 0, n, vl1 + 1, vl2);
                if ((vl1 + 1) % 2 != 0) swap(q2.first, q2.second);
                qu.insert({ q2.first, vl1 + 1, vl2 });
            }
            if (vl2 != r - 1) {
                pair<ll, ll> q = get(0, 0, n, vl2 + 1, r);
                if ((vl2 + 1) % 2 != 0) swap(q.first, q.second);
                qu.insert({ q.first, vl2 + 1, r });
            }
        }
    }
}

int main()
{
    fastInp;

    ll t = 1;

    while (t--) {
        input();
        sol();

        for (auto cur : ans) cout << cur << " ";
    }

    return 0;
}

Measured memory_bytes: 19156