#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using u64 = uint_fast64_t;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007;
//constexpr long long MOD = 998244353;
template<class T1, class T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return true;} return false; }
template<class T1, class T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return true;} return false; }
inline int popcount(int x) {return __builtin_popcount(x);}
inline int popcount(long long x) {return __builtin_popcountll(x);}
void print() { cout << "\n"; }
template<class T, class... Args>
void print(const T &x, const Args &... args) {
    cout << x << " ";
    print(args...);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////

template<typename T, typename Monoid>
struct SegmentTree {
    T unity;
    Monoid merge;
    int N;
    vector<T> node;

    SegmentTree(Monoid f, T id) : merge(f), unity(id) {}

    void init(int sz) {
        N = 1;
        while (N < sz) N *= 2;
        node.assign(2*N,unity);
    }

    void set(int k, const T &val) {node[k+N] = val;}

    void build() {
        for (int i = N-1; i > 0; --i) {
            node[i] = merge(node[i<<1|0], node[i<<1|1]);
        }
    }

    // (0-indexed)
    void update(int x, T val) {
        x += N;
        node[x] = val;
        while (x > 1) {
            x >>= 1;
            node[x] = merge(node[x<<1|0], node[x<<1|1]);
        }
    }

    // [l, r) (0-indexed)
    T get(int l, int r) {
        if (l >= r) return unity;
        T resl = unity, resr = unity;
        l += N; r += N;
        while (l < r) {
            if (l & 1) resl = merge(resl, node[l++]);
            l >>= 1;
            if (r & 1) resr = merge(node[--r], resr);
            r >>= 1;
        }
        return merge(resl, resr);
    }

    T operator[](int x) {return node[x+N];}
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N; cin >> N;
    vector<int> p(N);
    rep(i,N) cin >> p[i];

    auto f=[](pii a, pii b) {return min(a,b);};
    const pii id = pii(1e9,1e9);
    SegmentTree<pii, decltype(f)> odd(f,id), even(f,id);
    odd.init(N); even.init(N);
    rep(i,N) {
        if (i&1) odd.set(i,pii(p[i],i));
        else even.set(i,pii(p[i],i));
    }
    odd.build(); even.build();

    using Tu = tuple<pii, int, int>;
    priority_queue<Tu, vector<Tu>, greater<Tu>> pq;
    pq.emplace(even.get(0,N),0,N);

    vector<int> ans(N);
    int cur = 0;
    while (!pq.empty()) {
        pii vall,valr;
        int l,r;
        tie(vall,l,r) = pq.top(); pq.pop();
        ans[cur++] = vall.first;
        int ll = vall.second;
        valr = (l&1) ? even.get(ll+1,r) : odd.get(ll+1,r);
        ans[cur++] = valr.first;
        int rr = valr.second;
        if (l != ll) {
            pq.emplace(Tu((l&1) ? odd.get(l,ll) : even.get(l,ll), l, ll));
        }
        if (ll+1 != rr) {
            pq.emplace(Tu((ll&1) ? even.get(ll+1,rr) : odd.get(ll+1,rr), ll+1, rr));
        }
        if (rr+1 != r) {
            pq.emplace(Tu((rr&1) ? even.get(rr+1,r) : odd.get(rr+1,r), rr+1, r));
        }
        //cout << vall.first << " " << vall.second << " " << valr.first << " " << valr.second << endl;
    }

    rep(i,N) cout << ans[i] << " ";
    cout << ln;
}

Measured memory_bytes: 12024