#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
typedef pair<ll, int> Pl;
typedef pair<int, pair<int, int>> PP;
const double PI = 3.1415926535897932;   // acos(-1)
const double EPS = 1e-15;
const ll mod = 1e+9 + 7;
const int INF = 1001001001;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define chadd(x, y) x = (x + y) % mod

template<typename Monoid>
struct SegmentTree{
    using F = function<Monoid(Monoid, Monoid)>;

    int sz;
    vector<Monoid> seg;

    const F f;      // モノイドに対して二項演算を行う関数オブジェクト
    const Monoid M1;

    SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1){
        sz = 1;
        while(sz < n)   sz <<= 1;
        seg.assign(2 * sz, M1);
    }

    void set(int k, const Monoid &x){
        seg[k + sz] = x;
    }

    void build(){
        for(int k = sz - 1; k > 0; --k){
            seg[k] = f(seg[k << 1], seg[k << 1 | 1]);
        }
    }

    void update(int k, const Monoid &x){
        k += sz;
        seg[k] = x;
        while(k >>= 1){
            seg[k] = f(seg[k << 1], seg[k << 1 | 1]);
        }
    }

    Monoid query(int a, int b){
        Monoid L = M1, R = M1;
        for(a += sz, b += sz; a < b; a >>= 1, b >>= 1){
            if(a & 1)   L = f(L, seg[a++]);
            if(b & 1)   R = f(seg[--b], R);
        }
        return f(L, R);
    }

    Monoid operator[](const int &k) const{
        return seg[k + sz];
    }
};

int n;
vector<int> p;
SegmentTree<P> segeven(200005, [](P a, P b){return min(a, b);}, P(INF, INF));
SegmentTree<P> segodd(200005, [](P a, P b){return min(a, b);}, P(INF, INF));
priority_queue<PP, vector<PP>, greater<PP>> que;

// 区間[left, right) を分割し、区間 [left, right) における辞書順最小を返す
P split(int left, int right){
    int foo = -1, bar = -1;
    if(right - left < 2)    return P(foo, bar);

    if(left % 2 == 0){
        P pl = segeven.query(left, right);
        foo = pl.first;
        int posl = pl.second;
        P pr = segodd.query(posl + 1, right);
        bar = pr.first;
        int posr = pr.second;
        if(posl - left > 1){
            int ele = segeven.query(left, posl).first;
            que.push(PP(ele, P(left, posl)));
        }
        if(posr - (posl + 1)){
            int ele = segodd.query(posl + 1, posr).first;
            que.push(PP(ele, P(posl + 1, posr)));
        }
        if(right - (posr + 1)){
            int ele = segeven.query(posr + 1, right).first;
            que.push(PP(ele, P(posr + 1, right)));
        }
    }
    else{
        P pl = segodd.query(left, right);
        foo = pl.first;
        int posl = pl.second;
        P pr = segeven.query(posl + 1, right);
        bar = pr.first;
        int posr = pr.second;
        if(posl - left > 1){
            int ele = segodd.query(left, posl).first;
            que.push(PP(ele, P(left, posl)));
        }
        if(posr - (posl + 1)){
            int ele = segeven.query(posl + 1, posr).first;
            que.push(PP(ele, P(posl + 1, posr)));
        }
        if(right - (posr + 1)){
            int ele = segodd.query(posr + 1, right).first;
            que.push(PP(ele, P(posr + 1, right)));
        }
    }

    return P(foo, bar);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    p.resize(n);
    for(int i = 0; i < n; ++i){
        cin >> p[i];
        if(i % 2 == 0)  segeven.update(i, P(p[i], i));
        else    segodd.update(i, P(p[i], i));
    }
    que.push(PP(0, P(0, n)));
    while(!que.empty()){
        PP hoge = que.top();
        que.pop();
        int left = hoge.second.first, right = hoge.second.second;
        P foo = split(left, right);
        cout << foo.first << " " << foo.second;
        if(!que.empty())    cout << " ";
        else    cout << endl;
    }
}

Measured memory_bytes: 11264