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

const int MAX = 200000;

template<typename M>
struct SegmentTree {
    using F = function<M(M, M)>;
    const F f;
    const M m1;
    vector<M> nodes;
    int n;

    explicit SegmentTree(const vector<M> &v,
                         const F f, const M m1) : f(f), m1(m1) {
        n = 2;
        while (n < v.size()) n *= 2;
        nodes.resize(2 * n - 1, m1);
        for (int i = 0; i < v.size(); i++) {
            nodes[i + n - 1] = v[i];
        }
        for (int i = n - 2; i >= 0; i--) {
            nodes[i] = f(nodes[2 * i + 1], nodes[2 * i + 2]);
        }
    }
    void set(int pos, M val) {
        int idx = n - 1 + pos;
        nodes[idx] = val;
        do {
            idx = (idx - 1) / 2;
            nodes[idx] = f(nodes[2 * idx + 1], nodes[2 * idx + 2]);
        } while (idx != 0);
    }
    // l 番目から r - 1 番目の範囲の結果を出力する
    M get(int l, int r, int k = 0, int cl = 0, int cr = -1) {
        if (cr == -1) cr = n;
        if (l <= cl && cr <= r) return nodes[k];
        if (r <= cl || cr <= l) return m1;
        int m = (cl + cr) / 2;
        return f(get(l, r, 2 * k + 1, cl, m), get(l, r, 2 * k + 2, m, cr));
    }
};

vector<SegmentTree<int>> segs;
vector<int> indices;

struct IndexPair {
    int l, r;
    int l1, r1, r2;
    bool isOdd;
    IndexPair(int l, int r) : l(l), r(r) {
        l1 = l;
        if (l % 2 == r % 2) {
            r1 = r;
            r2 = r - 1;
        } else {
            r1 = r - 1;
            r2 = r;
        }
        isOdd = (l % 2 == 1);
        l1 /= 2;
        r1 /= 2;
        r2 /= 2;
    }
    bool operator<(const IndexPair &a) const {
        return segs[isOdd].get(l1, r1 + 1) >
               segs[a.isOdd].get(a.l1, a.r1 + 1);
    }
    pair<int, int> get() {
        int i = segs[isOdd].get(l1, r1 + 1);
        return make_pair(i,
                         segs[!isOdd].get((indices[i] + 1) / 2, r2 + 1));
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N;
    scanf("%d", &N);
    indices.resize(N+1);

    vector<int> veven(N / 2, MAX), vodd(N / 2, MAX);
    for (int i = 0; i < N / 2; i++) {
        int a, b;
        scanf("%d", &a);
        vodd[i] = a;
        indices[a] = i * 2;
        scanf("%d", &b);
        veven[i] = b;
        indices[b] = i * 2 + 1;
    }
    // 偶数番目と奇数番目の MRQ を作成
    SegmentTree<int> even(veven, [](int a, int b) {return min(a, b);}, MAX),
                     odd(vodd, [](int a, int b) {return min(a, b);}, MAX);
    segs.push_back(odd);
    segs.push_back(even);
    vector<vector<int>> vecs = {vodd, veven};

    priority_queue<IndexPair> que;
    IndexPair p(0, N - 1);
    bool f = false;
    que.push(p);
    while (!que.empty()) {
        IndexPair p = que.top();
        que.pop();
        if (f) printf(" ");
        int m, n;
        tie(m, n) = p.get();
        printf("%d %d", m, n);
        f = true;
        if (p.l < indices[m] - 1) {
            IndexPair p1(p.l, indices[m] - 1);
            que.push(p1);
        }
        if (indices[m] + 1 < indices[n] - 1) {
            IndexPair p2(indices[m] + 1, indices[n] - 1);
            que.push(p2);
        }
        if (indices[n] + 1 < p.r) {
            IndexPair p3(indices[n] + 1, p.r);
            que.push(p3);
        }
    }
    printf("\n");

    return 0;
}


Measured memory_bytes: 10492