#include "bits/stdc++.h"
using namespace std;

#define OUT(x)  cerr << #x << " = " << x << endl;
#define all(x)  x.begin(), x.end()
#define mp      make_pair
#define pii     pair<int, int>
#define piii    pair<int, pair<int, int>>

static const int INF = 0x3f3f3f3f;

template<typename Type>
struct SegmentTree {
        vector<Type> data;
        int n;
        SegmentTree(int x) {
                n = pow(2, ceil(log2(x)));
                data.resize(2 * n - 1);
                for (int i = 0; i < 2 * n - 1; i ++) data[i] = mp(INF, i - n + 1) ; //初期値
        }
        Type merge(Type x, Type y) { //更新関数
                if (x.first < y.first) return x;
                else return y;
        }
        void update(int k, int p) { //k番目をpで更新する
                k += n - 1;
                data[k].first = p;
                while (k > 0) {
                        k = (k - 1) / 2;
                        data[k] = merge(data[k * 2 + 1], data[k * 2 + 2]);
                }
        }
        // [l, r)
        Type query(int a, int b) { return query(a, b, 0, 0, n); }
        Type query(int a, int b, int k, int l, int r) {
                if (r <= a || b <= l) return mp(INF, -1); //初期値
                if (a <= l && r <= b) return data[k];
                int m = (l + r) / 2;
                return merge(query(a, b, k * 2 + 1, l, m), query(a, b, k * 2 + 2, m, r));
        }
};
                                   
int main() {
        int i, j;
        int n;
        cin >> n;
        vector<int> p(n);
        for (i = 0; i < n; i ++) cin >> p[i];
        SegmentTree<pii> st_even(n), st_odd(n);
        for (int i = 0; i < n; i ++) {
                if (i & 1) st_odd.update(i, p[i]); else st_even.update(i, p[i]);
        }
        priority_queue<piii, vector<piii>, greater<piii>> pq;
        pq.push(mp(st_even.query(0, n).first, mp(0, n)));
        vector<int> ans(n);
        int ansi = 0;
        while (!pq.empty()) {
                piii get = pq.top(); pq.pop();
                pii segment = get.second;
                int a, b;
                pii get1, get2;
                if (segment.first & 1) get1 = st_odd.query(segment.first, segment.second);
                else get1 = st_even.query(segment.first, segment.second);
                a = get1.second;
                ans[ansi ++] = get1.first;
                if (a & 1) get2 = st_even.query(a, segment.second);
                else get2 = st_odd.query(a, segment.second);
                b = get2.second;
                ans[ansi ++] = get2.first;
                if (segment.first < a) { 
                        if (segment.first & 1) pq.push(mp(st_odd.query(segment.first, a).first, mp(segment.first, a)));
                        else  pq.push(mp(st_even.query(segment.first, a).first, mp(segment.first, a)));
                }
                if (a + 1 < b) { 
                        if ((a + 1) & 1) pq.push(mp(st_odd.query(a + 1, b).first, mp(a + 1, b)));
                        else pq.push(mp(st_even.query(a + 1, b).first, mp(a + 1, b)));
                }
                if (b + 1 < segment.second) {
                        if ((b + 1) & 1) pq.push(mp(st_odd.query(b + 1, segment.second).first, mp(b + 1, segment.second)));
                        else pq.push(mp(st_even.query(b + 1, segment.second).first, mp(b + 1, segment.second)));
                }
        }
        for (int i = 0; i < n; i ++) cout << ans[i] << (i == n - 1 ? '\n' : ' ');
        return 0;
}



Measured memory_bytes: 11896