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

using ll = long long;
using pii = pair<int, int>;

struct rmq {
    using type = pii;
    static type id() {
        return make_pair(std::numeric_limits<int>::max(), std::numeric_limits<int>::max());
    }
    static type op(type const& l, type const& r) {
        return std::min(l, r);
    }
};

template<typename Monoid>
class segment_tree {
    using T = typename Monoid::type;

public:
    segment_tree(std::vector<T> const& init)
        : sz(init.size()),
          n(expand(init.size()))
    {
        dat.assign(n*2, Monoid::id());
        std::copy(begin(init), end(init), begin(dat) + n);
        for(int i = n - 1; i >= 0; --i) {
            dat[i] = Monoid::op(dat[i * 2], dat[i * 2 + 1]);
        }
    }

    segment_tree(int const n, T const& init = Monoid::id())
        : segment_tree(std::vector<T>(n, init))
    {}

    void update(int p, T val) {
        assert(0 <= p && p < sz);
        dat[p += n] = val;
        while(p /= 2) {
            dat[p] = Monoid::op(dat[p * 2], dat[p * 2 + 1]);
        }
    }

    // [l, r)
    T query(int l, int r) const {
        assert(0 <= l && l <= r && r <= sz);
        l += n;
        r += n;
        T res1 = Monoid::id(),
          res2 = Monoid::id();
        while(l != r) {
            if(l & 1) {
                res1 = Monoid::op(res1, dat[l++]);
            }
            if(r & 1) {
                res2 = Monoid::op(dat[--r], res2);
            }
            l /= 2;
            r /= 2;
        }
        return Monoid::op(res1, res2);
    }

    int size() const {
        return sz;
    }

private:
    int expand(int n) const {
        return n == 1 ? n : expand((n + 1) / 2) * 2;
    }

private:
    const int sz;
    const int n;
    std::vector<T> dat;
};


struct section {
    pii ml, mr;
    int l, r;
    section(int l_, int r_, segment_tree<rmq>& seg1, segment_tree<rmq>& seg2) {
        l = l_;
        r = r_;
        if(l & 1) {
            ml = seg2.query(l, r);
            mr = seg1.query(ml.second + 1, r);
        } else {
            ml = seg1.query(l, r);
            mr = seg2.query(ml.second + 1, r);
        }
    }
    bool operator<(section const& s) const {
        auto m1 = make_pair(ml.first, mr.first);
        auto m2 = make_pair(s.ml.first, s.mr.first);
        return m1 > m2;
    }
};


int main() {
    int N;
    cin >> N;
    vector<int> a(N);
    segment_tree<rmq> seg1(N), seg2(N);
    for(int i = 0; i < N; ++i) {
        cin >> a[i];
        if(i & 1) {
            seg2.update(i, make_pair(a[i], i));
        } else {
            seg1.update(i, make_pair(a[i], i));
        }
    }

    vector<int> res;
    priority_queue<section> que;
    que.push(section(0, N, seg1, seg2));
    while(!que.empty()) {
        auto sec = que.top();
        que.pop();
        res.push_back(sec.ml.first);
        res.push_back(sec.mr.first);
        if(sec.l != sec.ml.second) {
            que.push(section(sec.l, sec.ml.second, seg1, seg2));
        }
        if(sec.ml.second + 1 != sec.mr.second) {
            que.push(section(sec.ml.second + 1, sec.mr.second, seg1, seg2));
        }
        if(sec.mr.second + 1 < sec.r) {
            que.push(section(sec.mr.second + 1, sec.r, seg1, seg2));
        }
    }
    
    for(int i = 0; i < N; ++i) {
        cout << res[i] << " \n"[i == N - 1] << flush;
    }
}


Measured memory_bytes: 14328