/*Bismillahir Rahmanir Rahim*///{
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using ull = unsigned long long; using ld = long double;
const ll llinf = (1ll<<61)-1;
const double eps = 1e-6, ldeps = 1e-9;
struct Dbg {
static constexpr auto &os = cout;   // replace by cerr in interactive.
template<class C> static auto dud(C *x)->decltype(os << *x, 0);
template<class C> static char dud(...);
template<class C> typename enable_if<sizeof dud<C>(0)!=1, Dbg&>::type operator<<(const C &x) { os << x; return *this; }
template<class C> Dbg &dump(C b, C e) {
    *this << "\n[";
    int cur = 0;
    for (C i = b; i!=e and cur<26; i++, cur++) *this << ", "+2*(i==b) << *i;
    return *this << ']';
}
template<class C> typename enable_if<sizeof dud<C>(0)==1, Dbg&>::type operator<<(const C &x) {
    return dump(begin(x), end(x));
}
template<class C, size_t X> typename enable_if<sizeof(C)!=1, Dbg&>::type operator <<(C (&x)[X]) {
    return dump(begin(x), end(x));
}
template<class B, class C> Dbg &operator <<(const pair<B, C> &x) {
    return *this << '{' << x.first << ", " << x.second << '}';
}
template<class C, size_t Y> struct TP {
    void operator()(Dbg& os, const C &t) { TP<C, Y-1>()(os, t); os << ", " << get<Y-1>(t); }
};
template<class C> struct TP<C, 1> { void operator()(Dbg& os, const C &t) { os << get<0>(t); } };
template<class... C> Dbg& operator<<(const tuple<C...> &t) {
    os << '{', TP<decltype(t), sizeof...(C)>()(*this, t); return *this << '}';
}
Dbg &operator<<(ostream&(*x)(std::ostream&)) { os << x; return *this; }
} dbg;
void err(istringstream *iss) { delete iss; }
template<class C, class... Args> void err(istringstream *iss, const C &val, const Args &... args) {
    string name; *iss >> name; if (name.back()==',') name.pop_back();
    dbg << name << " = " << val << "; ", err(iss, args ...);
}
#define bug(args...) dbg << __LINE__ << ": ", err(new istringstream(string(#args)), args), dbg << endl
#define sl(a) int(strlen(a))
#define sz(a) int(a.size())
int T, Q, cn;//}
const int inf = 1000000007, mxn = 200005;


template<class T, int N, class cmp = less<T>> class SparseTable
{
    int lookup[22][N+2], log_2[N+2];
public:
    T ara[N+2];

    SparseTable() {
        log_2[1] = 0;
        for (int i = 2; i<N; i++) log_2[i] = log_2[i>>1]+1;
    }

    void preprocess(int _n) {   // first assign to its member ara.
        for (int i = 0; i < _n; i++) lookup[0][i] = i;
        for (int j = 1; (1<<j)<=_n; j++) {
            for (int i = 0; (i+(1<<j)-1) < _n; i++) {
                lookup[j][i] = cmp()(ara[lookup[j-1][i]], ara[lookup[j-1][i+(1<<(j-1))]]) ? lookup[j-1][i] : lookup[j-1][i+(1<<(j-1))];
            }
        }
    }

    int query(int L, int R) {   // Returns minimum of ara[L..R] based on cmp().
        int j = log_2[R-L+1];
        return cmp()(ara[lookup[j][L]], ara[lookup[j][R-(1<<j)+1]]) ? lookup[j][L] : lookup[j][R-(1<<j)+1];
        // return cmp()(ara[lookup[j][L]], ara[lookup[j][R-(1<<j)+1]]) ? ara[lookup[j][L]] : ara[lookup[j][R-(1<<j)+1]];
    }
};

int n, p[mxn];
SparseTable<int, mxn> stEven, stOdd;

list<int> g[mxn];
int cntNode;
pair<int, int> bestPair[mxn];

pair<int, int> bestPairIdx(int l, int r) {
    if (l&1) {
        int nl = stOdd.query(l, r);
        return {nl, stEven.query(nl+1, r)};
    } else {
        int nl = stEven.query(l, r);
        return {nl, stOdd.query(nl+1, r)};
    }
}

int rec(int l, int r) {
    if (l>r) return inf;
    auto o = bestPairIdx(l, r);
    int nl = o.first, nr = o.second;
    int left = rec(l, nl-1), mid = rec(nl+1, nr-1), right = rec(nr+1, r);
    bestPair[++cntNode] = {p[nl], p[nr]};
    if (left!=inf) g[cntNode].push_back(left);
    if (mid!=inf) g[cntNode].push_back(mid);
    if (right!=inf) g[cntNode].push_back(right);
    return cntNode;
}

struct cmp { bool operator() (const int &ls, const int &rs) const {
    return bestPair[ls]>bestPair[rs];
}};

priority_queue<int, vector<int>, cmp> pq;
int topsort[mxn], tsi, indeg[mxn];
void lexiMinTopSort(int mnNode, int mxNode) {
    tsi = 0;
    for (int i = mnNode; i <= mxNode; i++) {
        for (auto &j : g[i]) {
            indeg[j]++;
        }
    }
    for (int i = mnNode; i <= mxNode; i++) {
        if (!indeg[i]) pq.push(i);
    }
    while (!pq.empty()) {
        int u = pq.top();
        pq.pop();
        topsort[tsi++] = u;
        for (auto &v : g[u]) {
            indeg[v]--;
            if (!indeg[v]) pq.push(v);
        }
    }
}

signed main() { ios::sync_with_stdio(0); cin.tie(NULL); cout.precision(11);
/*
Obviously we will try to take the min and 2nd min at last, but only those pairs are takeable at last which have even
number of elements between them, to their left and to their right, those intervals must be handled first and there can be
mix between them, I can't find any other way to handle freely mixing between intervals than to use DAG + topsort_bfs,
notice that dfs gives us arbitrary topsort, but here we need lexicographically minimum topsort:
Let rec(l, r) be a recursive function to handle range (l, r). We choose the last pair, create a node for it and return node.
==> To handle even intervals, First index of the pair has to be of same parity as l (min of that parity), second
must be of different parity and to the right of first element. This pair creates at most 3 intervals, we will give edge to
all of them.
*/
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        stEven.ara[i] = i&1 ? inf : p[i], stOdd.ara[i] = i&1 ? p[i] : inf;
    }
    stEven.preprocess(mxn), stOdd.preprocess(mxn);
    rec(1, n);
    lexiMinTopSort(1, cntNode);
    for (int i = 0; i < tsi; i++) {
        cout << bestPair[topsort[i]].first << ' ' << bestPair[topsort[i]].second << " \n"[i==tsi-1];
    }
}

Measured memory_bytes: 49024