#include <bits/stdc++.h>

using namespace std;


#ifdef zxc

#include <sys/resource.h>
#include "debug.h"
#include "profile.h"

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define profile(X) LOG_DURATION(X)
#else
#define debug(...) 42
#define profile(...) 42
#endif

using ll = int64_t;
using ld = double;
const ld EPS = 1e-9;
//const ll MOD = 924844033;
const ld PI = 3.141592653589793;
const int maxn = 600001;
const int MOD = 1e9 + 7;
using cd = complex<double>;

void fast_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}


struct segtree {
    segtree(int sz) : data(4 * sz) {}

    void add(int v, int tl, int tr, int pos, pair<int, int> val) {
        if (tl == tr - 1) {
            data[v] = val;
            return;
        }
        int tm = (tl + tr) >> 1;
        if (tm > pos) {
            add(v << 1, tl, tm, pos, val);
        } else {
            add(v << 1 | 1, tm, tr, pos, val);
        }
        data[v] = min(data[v << 1], data[v << 1 | 1]);
    }

    pair<int, int> get_mn(int v, int tl, int tr, int l, int r) {
        if (tl >= r || l >= tr) {
            return {1e9, -1};
        }
        if (tl >= l && tr <= r) {
            return data[v];
        }
        int tm = (tl + tr) >> 1;
        return min(get_mn(v << 1, tl, tm, l, r),
                   get_mn(v << 1 | 1, tm, tr, l, r));
    }

    vector<pair<int, int>> data;
};

pair<int, int> calc_idx(int pos) {
    int x = pos % 2;
    if (x) {
        return {x, pos / 2};
    } else {
        return {x, (pos - 1) / 2};
    }
}

int close_parity(int pos, int b) {
    if (pos % 2 == b) {
        return pos;
    }
    return pos + 1;
}


signed main() {
#ifdef zxc
    struct rlimit rl;
    const rlim_t kStackSize = 512L * 1024L * 1024L;
    assert(!getrlimit(RLIMIT_STACK, &rl));
    rl.rlim_cur = kStackSize;
    assert(!setrlimit(RLIMIT_STACK, &rl));
    freopen("../input.txt", "r", stdin);
//    freopen("../kolya_output.txt", "w", stdout);
#else
    //    mt19937 mt(std::chrono::high_resolution_clock::now().time_since_epoch().count());
    //            freopen("", "r", stdin);
    //        freopen("hack.out", "w", stdout);
#endif
    profile("all");

    auto solve = [](int _) {
        int n;
        cin >> n;
        vector<int> p(n + 1);
        for (int i = 1; i <= n; ++i) {
            cin >> p[i];
        }
        vector<segtree> segtrees;
        segtrees.emplace_back(n + 1);
        segtrees.emplace_back(n + 1);
        for (int i = 1; i <= n; ++i) {
            int a, b;
            tie(a, b) = calc_idx(i);
            segtrees[a].add(1, 0, n + 1, b, {p[i], i});
        }

        function<pair<int, int>(int, int)> get_best = [&](int l, int r) -> pair<int, int> {
            if (l == r - 1) {
                assert(false);
            }
            auto seg_pos = calc_idx(l);
            auto seg_pos2 = calc_idx(close_parity(r, l % 2));
            auto mn = segtrees[seg_pos.first].get_mn(1, 0, n + 1, seg_pos.second, seg_pos2.second);
            int ind = mn.second;
            int l1 = ind + 1;
            auto seg_pos3 = calc_idx(l1);
            auto seg_pos4 = calc_idx(close_parity(r, l1 % 2));
            auto mn2 = segtrees[seg_pos3.first].get_mn(1, 0, n + 1, seg_pos3.second, seg_pos4.second);
            return {mn.second, mn2.second};
        };
        set<tuple<int, int, int>> ss;
        auto xx = get_best(1, n + 1);

        ss.emplace(p[xx.first], 1, n + 1);
        vector<int> ans;
        while (!ss.empty()) {
            int val, l, r;
            tie(val, l, r) = *ss.begin();
            ss.erase(ss.begin());

            auto xx = get_best(l, r);
            ans.push_back(p[xx.first]);
            ans.push_back(p[xx.second]);
            auto ijorgejipoke = [&](int l, int r) {
                if (l + 1 >= r) {
                    return;
                }
                auto efew = get_best(l, r);
                ss.emplace(p[efew.first], l, r);
            };
            ijorgejipoke(l, xx.first);
            ijorgejipoke(xx.first + 1, xx.second);
            ijorgejipoke(xx.second + 1, r);
        }
        for (auto b: ans) {
            cout << b << " ";
        }
    };


    fast_io();
    cout.precision(9);
    cout << fixed;

    solve(1);


}


Measured memory_bytes: 18164