#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <queue>
#include <functional>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const ll MOD = 1000000007;

const int INF = 100000000;

class IndexSegmentTree {
private:
    int n;
    vector<int> dat;
    vector<int> v;
public:
    void init(int n_) {
        n = 1;
        while (n < n_) n *= 2;
        dat.assign(2 * n - 1, -1);
        v.assign(n, INF);
    }
    // k: index(0-indexed), a: value
    void update(int p, int a) {
        v[p] = a;
        int k = p + n - 1;
        dat[k] = p;
        while (k>0) {
            k = (k - 1) / 2;
            if (dat[k * 2 + 1] == -1) {
                dat[k] = dat[k * 2 + 2];
            }else if (dat[k * 2 + 2] == -1 || v[dat[k * 2 + 1]] <= v[dat[k * 2 + 2]]) {
                dat[k] = dat[k * 2 + 1];
            }else {
                dat[k] = dat[k * 2 + 2];
            }
        }
    }
    // query(a, b) =>  minimum in [a,b]
    int query(int a, int b) {
        return _query(a, b, 0, 0, n - 1);
    }
    // v[dat[k]] is minimum in [l,r]
    int _query(int a, int b, int k, int l, int r) {
        if (r<a || b<l) return -1;
        if (a <= l&&r <= b) {
            return dat[k];
        }
        else {
            int vl = _query(a, b, k * 2 + 1, l, (l + r) / 2);
            int vr = _query(a, b, k * 2 + 2, (l + r) / 2 + 1, r);
            if (vr == -1) {
                return vl;
            }
            else if (vl == -1) {
                return vr;
            }
            else {
                if (v[vl] > v[vr]) {
                    return vr;
                }
                else {
                    return vl;
                }
            }
        }
    }
    // k: index(0-indexed)
    int get(int k) {
        return v[k];
    }
};

IndexSegmentTree seg[2];
vector<int> p;
vector<P> pairs;
vector<vector<int>> G;


int dfs(int l, int r, int m) {
    // [l, r]
    int min_idx = seg[m].query(l, r);
    assert(min_idx != -1);
    int next_m = m ^ 1;
    int pair_idx = seg[next_m].query(min_idx + 1, r);
    // assert(pair_idx != -1);

    int i = pairs.size();
    assert(i == G.size());
    pairs.emplace_back(p[min_idx], p[pair_idx]);
    G.push_back({});

    if (l < min_idx - 1) {
        G[i].push_back(dfs(l, min_idx - 1, m));
    }
    if (min_idx + 1 < pair_idx - 1) {
        G[i].push_back(dfs(min_idx + 1, pair_idx - 1, next_m));
    }
    if (pair_idx + 1 < r) {
        G[i].push_back(dfs(pair_idx + 1, r, m));
    }

    return i;
}

int main() {
    int N;
    cin >> N;

    seg[0].init(N);
    seg[1].init(N);

    p.resize(N);
    for (int i = 0; i<N; i++) {
        cin >> p[i];
        seg[i % 2].update(i, p[i]);
    }

    int root = dfs(0, N - 1, 0);
    // assert(root == 0);

    priority_queue<P, vector<P>, greater<P>> que;
    que.emplace(pairs[root].first, root);

    bool start = true;
    while (que.size()) {
        P p = que.top(); que.pop();
        int v = p.second;
        if (!start) {
            cout << " ";
        }
        start = false;
        cout << pairs[v].first << " " << pairs[v].second;
        for (int to : G[v]) {
            que.emplace(pairs[to].first, to);
        }
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 26152