#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll INF = 1e9;
const ll MOD = 1e9 + 7;
const double EPS = 1e-8;

template<typename T> T chmax(T& a, const T& b){return a = (a > b ? a : b);}
template<typename T> T chmin(T& a, const T& b){return a = (a < b ? a : b);}

/*
    遅延伝搬 segment tree
    (区間更新、最小値取得)
    
    verified : AOJ DSL2 F
*/
template <typename T>
struct SegTree {
    int n;
    vector<T> dat, lazy;
    const T NIL = 2e18;
    const T DFLT;    // 範囲外で返す値 minQuery -> 1e18, maxQuery -> -1e18
    SegTree(int n_, const T& initV, const T& dflt) : DFLT(dflt) {
        n = 1;
        while (n < n_) n *= 2;
        dat.assign(2 * n - 1, initV);
        lazy.assign(2 * n - 1, NIL);
    }
    void add(int l, int r, const T& t) {
        add(l, r, t, 0, 0, n);
    }
    T query(int l, int r) {
        return query(l, r, 0, 0, n);
    }
private:
    T f(const T& a, const T& b) {
        return min(a, b);
    }
    void fix(int k) {
        dat[k] = f(dat[k * 2 + 1], dat[k * 2 + 2]);
    }
    void setLazy(int k, const T& v) {
        lazy[k] = v;
        dat[k] = v;
    }
    void push(int k) {
        if (lazy[k] == NIL) return;
        setLazy(k * 2 + 1, lazy[k]);
        setLazy(k * 2 + 2, lazy[k]);
        lazy[k] = NIL;
    }
    void add(int queryL, int queryR, const T& val, int k, int nodeL, int nodeR) {
        // クエリ区間とノード区間が交差していないなら、これ以上、処理する意味はない
        if (nodeR <= queryL || queryR <= nodeL) {
            return;
        }
        // ノード区間がクエリ区間に完全に覆われたら、遅延命令をセットして、さっさと帰る
        if (queryL <= nodeL && nodeR <= queryR) {
            setLazy(k, val);
            return;
        }
        // ノードが下がるときには命令をpushする
        push(k);
        int nodeM = (nodeL + nodeR) / 2;
        add(queryL, queryR, val, k * 2 + 1, nodeL, nodeM);
        add(queryL, queryR, val, k * 2 + 2, nodeM, nodeR);

        // ノードが上がるときには情報をfixする
        fix(k);
    }
    T query(int queryL, int queryR, int k, int nodeL, int nodeR) {
        // クエリ区間とノード区間が交差していない
        if (nodeR <= queryL || queryR <= nodeL) {
            return DFLT;
        }
        // ノード区間がクエリ区間に完全に覆われた
        if (queryL <= nodeL && nodeR <= queryR) {
            return dat[k];
        }
        // ノードが下がるときには命令をpushする
        push(k);
        int nodeM = (nodeL + nodeR) / 2;
        T vl = query(queryL, queryR, k * 2 + 1, nodeL, nodeM);
        T vr = query(queryL, queryR, k * 2 + 2, nodeM, nodeR);
        return f(vl, vr);
    }
};

int main(){
    int n;
    cin >> n;
    vi p(n);
    rep(i, n) cin >> p[i];
    SegTree<ll> odd(n, INF, INF);
    SegTree<ll> even(n, INF, INF);

    vi idx(n+1, -1);
    rep(i, n) idx[p[i]] = i;

    rep(i, n) {
        if(i&1) odd.add(i, i+1, p[i]);
        else even.add(i, i+1, p[i]);
    }
    using P = pair<int, pair<int, int>>;
    priority_queue<P, vector<P>, greater<P> > q;
    q.push(make_pair(even.query(0, n), make_pair(0, n)));
    vi ans;
    while(!q.empty()) {
        auto p = q.top(); q.pop();
        int a = p.fi, l = p.se.fi, r = p.se.se;
        SegTree<ll>& cur = (idx[a]&1 ? odd : even);
        SegTree<ll>& nxt = (idx[a]&1 ? even : odd);

        if(cur.query(idx[a], idx[a]+1) == INF) continue;

        int b = nxt.query(idx[a], r);

        ans.push_back(a);
        ans.push_back(b);

        cur.add(idx[a], idx[a]+1, INF);
        nxt.add(idx[b], idx[b]+1, INF);

        if(l != idx[a]) q.push(make_pair(cur.query(l, idx[a]), make_pair(l, idx[a])));
        if(idx[a] + 1 != idx[b]) q.push(make_pair(nxt.query(idx[a]+1, idx[b]), make_pair(idx[a]+1, idx[b])));
        if(idx[b] + 1 != r) q.push(make_pair(cur.query(idx[b]+1, r), make_pair(idx[b]+1, r)));
    }
    rep(i, n) {
        cout << ans[i] << (i+1 == n ? '\n' : ' ');
    }
    return 0;
}

Measured memory_bytes: 20904