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

static const int INF = 0x3f3f3f3f;

struct SegmentTree {
        vector<pair<int, int>> data; //minとnode_number
        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].first = INF;
                        data[i].second = i - n + 1;
                }
        }
        //k番目を更新する
        void update(int k, int p) {
                k += n - 1;
                data[k].first = p;
                while (k > 0) {
                        k = (k - 1) / 2;
                        if (data[k * 2 + 1].first < data[k * 2 + 2].first) {
                                data[k].first = data[k * 2 + 1].first;
                                data[k].second = data[k * 2 + 1].second;
                        } else {
                                data[k].first = data[k * 2 + 2].first;
                                data[k].second = data[k * 2 + 2].second;
                        }
                }
        }
        // [l, r)
        pair<int, int> query(int a, int b) { return query(a, b, 0, 0, n); }
        pair<int, int> query(int a, int b, int k, int l, int r) {
                if (r <= a || b <= l) return make_pair(INF, 0);
                if (a <= l && r <= b) return data[k];
                int m = (l + r) / 2;
                pair<int, int> left = query(a, b, k * 2 + 1, l, m);
                pair<int, int> right = query(a, b, k * 2 + 2, m, r);
                if (left.first < right.first) return left;
                else return right;
        }
};

#define mp make_pair

int main() {
        int n;
        cin >> n;
        vector<int> p(n);
        for (int i = 0; i < n; i ++) cin >> p[i];
        SegmentTree 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<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq; //(min, [l, r))をいれる
        pq.push(mp(st_even.query(0, n).first, mp(0, n)));
        vector<int> ans(n);
        int ansi = 0;
        while (!pq.empty()) {
                pair<int, pair<int, int>> get = pq.top(); pq.pop();
                pair<int, int> segment = get.second;
                int a, b;
                pair<int, int> 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