#include "bits/stdc++.h"
using namespace std;
using ll     = long long;
using pii    = pair<int, int>;
using pll    = pair<ll, ll>;
using vi     = vector<int>;
using vl     = vector<ll>;
using vvi    = vector<vi>;
using vvl    = vector<vl>;
const ll INF = 1LL << 60;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}
template <class C>
void print(const C &c, std::ostream &os = std::cout) {
    std::copy(std::begin(c), std::end(c), std::ostream_iterator<typename C::value_type>(os, " "));
    os << std::endl;
}

// 0-indexed bottom up Segment Tree
// UNIT is the identity element of operation func
template <typename T = int>
struct SegmentTree {
    using F = function<T(T, T)>;
    int n;
    vector<T> dat;
    F func;
    T UNIT;

    SegmentTree(int n_, F func_, T UNIT_) : func(func_), UNIT(UNIT_) {
        n = 1;
        // full binary tree: num of leaves = n = 2^k >= n_
        while (n < n_)
            n *= 2;
        dat.assign(2 * n - 1, UNIT);
    }
    SegmentTree(vector<T> v_, F func_, T UNIT_) : func(func_), UNIT(UNIT_) {
        n = 1;
        while (n < v_.size())
            n *= 2;
        dat.assign(2 * n - 1, UNIT);
        for (int i = 0; i < v_.size(); ++i) {
            dat[n - 1 + i] = v_[i];
        }
        for (int i = n - 2; i >= 0; --i) {
            dat[i] = func(dat[2 * i + 1], dat[2 * i + 2]);
        }
    }
    void update(int k, T a) {
        // leaves are at index n-1 to 2*n-2
        k += n - 1;
        dat[k] = a;
        while (k > 0) {
            // k -> parent node
            k = (k - 1) / 2;
            // func(child nodes)
            dat[k] = func(dat[2 * k + 1], dat[2 * k + 2]);
        }
    }
    // get result of func() in [l, r)
    T query(int l, int r) {
        l += n - 1;
        r += n - 1;
        T ret = UNIT;
        while (l < r) {
            if ((l & 1) == 0)
                ret = func(ret, dat[l]);
            if ((r & 1) == 0)
                ret = func(ret, dat[r - 1]);
            l = l / 2;
            r = (r - 1) / 2;
        }
        return ret;
    }
};

int main() {
    int n;
    cin >> n;
    vi p(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
    }
    auto f = [](pii l, pii r) { return min(l, r); };
    SegmentTree<pii> even(n, f, {10000000, -1});
    SegmentTree<pii> odd(n, f, {10000000, -1});
    for (int i = 0; i < n; ++i) {
        if (i % 2 == 0)
            even.update(i, {p[i], i});
        else
            odd.update(i, {p[i], i});
    }
    using piii = pair<int, pii>;
    priority_queue<piii, vector<piii>, greater<piii>> pq;
    vi ret;
    int mini = even.query(0, n).first;
    pq.push({mini, {0, n}});
    while (!pq.empty()) {
        auto p = pq.top();
        pq.pop();
        int l = p.second.first;
        int r = p.second.second;
        if (p.second.first % 2 == 0) {
            auto x = even.query(l, r);
            ret.push_back(x.first);
            auto y = odd.query(x.second, r);
            ret.push_back(y.first);
            if (x.second != l) {
                pq.push({even.query(l, x.second).first, {l, x.second}});
            }
            if (x.second + 1 != y.second) {
                pq.push({odd.query(x.second + 1, y.second).first, {x.second + 1, y.second}});
            }
            if (y.second + 1 != r) {
                pq.push({even.query(y.second + 1, r).first, {y.second + 1, r}});
            }
        } else {
            auto x = odd.query(l, r);
            ret.push_back(x.first);
            auto y = even.query(x.second, r);
            ret.push_back(y.first);
            if (x.second != l) {
                pq.push({odd.query(l, x.second).first, {l, x.second}});
            }
            if (x.second + 1 != y.second) {
                pq.push({even.query(x.second + 1, y.second).first, {x.second + 1, y.second}});
            }
            if (y.second + 1 != r) {
                pq.push({odd.query(y.second + 1, r).first, {y.second + 1, r}});
            }
        }
    }
    print(ret);
    return 0;
}

Measured memory_bytes: 11944