#include <bits/stdc++.h>

using namespace std;

using i64 = int64_t;

const i64 MOD = 1e9+7;

const i64 INF = 1e18+7;


using value_type = pair<int,int>;

class Node;
using np = Node*;

class Node{
public:

    static np nil;

    value_type val;
    uint32_t pri;
    np l = nil;
    np r = nil;

    int size;

    bool lazy_flag = false;

    value_type lazy_val = value_type();

    Node() : val(), pri(rndpri()), size(1), l(nil), r(nil){}
    Node(value_type v) : val(v), pri(rndpri()), size(1), l(nil), r(nil){}
    Node(value_type v, uint32_t p) : val(v), pri(p), size(1), l(nil), r(nil){}

    static uint32_t rndpri() {
        static uint32_t x = 123456789, y = 362436069, z = 521288629, w = time(0);
        uint32_t t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
        return max<uint32_t>(1, w & 0x3FFFFFFF);
    }
};

np Node::nil = new Node(value_type(), 0);

class Treap{

public:

    np root;

    Treap() : root(Node::nil){}

    Treap(value_type val) : root(new Node (val)){}

    // イテレータが指す[st,en)の範囲で初期化する
    Treap(vector<value_type>::iterator st, vector<value_type>::iterator en) : root(Node::nil){
        while(st != en){
            root = _merge(root, new Node(*st));
            ++st;
        }
    }

    // 配列で初期化する
    Treap(vector<value_type> v) : root(Node::nil){
        for(auto& xx : v)
            root = _merge(root, new Node(xx));
    }

    ~Treap(){
        // clear();
    }


protected:

    int _size(np x){return x == Node::nil ? 0 : x->size;}

    np _update(np x){

        if(x == Node::nil)
            return x;

        x->size = _size(x->l) + _size(x->r) + 1;
        return x;
    }

    np _merge(np l, np r){
        if(l == Node::nil || r == Node::nil)
            return l == Node::nil ? r : l;

        if(l->pri > r->pri){
            l->r = _merge(l->r, r);
            return _update(l);
        }else{
            r->l = _merge(l, r->l);
            return _update(r);
        }
    }

    pair<np,np> _split(np x, int k){
        if(x == Node::nil)
            return make_pair(Node::nil, Node::nil);

        if(k <= _size(x->l)){
            pair<np,np> s = _split(x->l, k);
            x->l = s.second;
            return make_pair(s.first, _update(x));

        }else{
            pair<np,np> s = _split(x->r, k - _size(x->l) - 1);
            x->r = s.first;
            return make_pair(_update(x), s.second);
        }
    }

    np _insert(np x, int k, value_type val){
        np l,r;
        tie(l, r) = _split(x, k);
        return _merge(_merge(l, new Node(val)), r);
    }

    np _erase(np x, int k){
        np l,r,m;
        tie(l, r) = _split(x, k);
        tie(m, r) = _split(r, 1);
        return _merge(l, r);
    }

    void _set(np x, int k, value_type val){
        _update(x);

        if(k < _size(x->l))
            _set(x->l, k, val);
        else if(_size(x->l) == k)
            x->val = val;
        else
            _set(x->r, k - _size(x->l) - 1, val);

        _update(x);
    }

    value_type _get(np x, int k){

        _update(x);

        if(k < _size(x->l))
            return _get(x->l, k);
        else if(_size(x->l) == k)
            return x->val;
        else
            return _get(x->r, k - _size(x->l) - 1);
    }

    int _lowerbound(np x, value_type val){
        _update(x);

        if(x == Node::nil)
            return 0;
        if(val <= x->val)
            return _lowerbound(x->l, val);
        else
            return _lowerbound(x->r,val) + _size(x->l) + 1;
    }

    int _upperbound(np x, value_type val){
        _update(x);

        if(x == Node::nil)
            return 0;
        if(val < x->val)
            return _upperbound(x->l, val);
        else
            return _upperbound(x->r,val) + _size(x->l) + 1;
    }

    np _insert(np x, value_type val){
        return _insert(x, _lowerbound(x, val), val);
    }

    void _clear(np x){
        if(x->l != Node::nil){
            _clear(x->l);
            delete(x->l);
            x->l = Node::nil;
        }
        if(x->r != Node::nil){
            _clear(x->r);
            delete(x->r);
            x->r = Node::nil;
        }
    }

public:

    void push_front(value_type val){
        root = _merge(new Node(val), root);
    }

    void push_back(value_type val){
        root = _merge(root, new Node(val));
    }

    void pop_front(){
        root = _split(root, 1).second;
    }

    void pop_back(){
        root = _split(root, _size(root) - 1).first;
    }

    // rootを含めたサイズの出力
    int size(){
        return (root == Node::nil ? 0 : root->size);
    }

    // k番目への代入
    void set(int k, value_type val){
        return _set(root, k, val);
    }

    // k番目の取得
    value_type get(int k){
        return _get(root, k);
    }

    // k番目への挿入
    void insert(int k, value_type val){
        root = _insert(root, k, val);
    }

    // 適切な位置への挿入
    void insert(value_type val){
        root = _insert(root, val);
    }

    // val <= get(k) となるような最小のk
    int lowerbound(value_type val){
        return _lowerbound(root, val);
    }

    // val < get(k) となるような最小のk
    int upperbound(value_type val){
        return _upperbound(root, val);
    }

    // k番目の要素削除
    void erase(int k){
        root = _erase(root, k);
    }

    // 要素の全削除
    void clear(){
        if(root != Node::nil){
            _clear(root);
            delete(root);
            root = Node::nil;
        }
    }
};



template<typename T>
struct Segtree{
    int n;
    T op;
    vector<T> elm;
    function<T(T, T)> f;

    Segtree(int n, T init, function<T(T, T)> f, T op = T()) :
        n(n),
        op(op),
        elm(2 * n, init),
        f(f)
    {
    }

    void set(int x, T val){
        x += n;
        elm[x] = val;
        while(x >>= 1)
            elm[x] = f(elm[2 * x], elm[2 * x + 1]);
    }

    void update(int x, T val){
        x += n;
        elm[x] = f(val, elm[x]);
        while(x >>= 1)
            elm[x] = f(elm[2 * x], elm[2 * x + 1]);
    }

    T get(int x, int y) const{
        T val = op;
        for(x += n, y += n - 1; x <= y; x >>= 1, y >>= 1){
            if(x & 1)
                val = f(val, elm[x++]);
            if(!(y & 1))
                val = f(val, elm[y--]);
        }
        return val;
    }
};

signed main(){

    int n;
    cin >> n;
    vector<int> a(n);
    for(auto& x : a){
        cin >> x;
        --x;
    }
    vector<Segtree<int>> seg(2, Segtree<int>(n, MOD, [](int x, int y){return min(x, y);}, MOD));
    for(int i = 0; i < n; ++i)
        seg[i & 1].set(i, a[i]);

    vector<int> inv(n);
    for(int i = 0; i < n; ++i)
        inv[a[i]] = i;

    function<Treap(int,int)> f = [&](int l, int r){
        // cout << "[" << l << "," << r << ")" << endl;
        // [l,r)の長さは必ず偶数になる
        Treap v;

        int t1 = seg[l & 1].get(l, r);
        int t2 = seg[(l & 1) ^ 1].get(inv[t1], r);
        vector<vector<int>> w = {{l, inv[t1]}, {inv[t1] + 1, inv[t2]}, {inv[t2] + 1, r}};

        vector<Treap> ret;

        for(auto& p : w){
            if(p[0] == p[1])
                continue;
            ret.emplace_back(f(p[0], p[1]));
        }
        sort(ret.begin(), ret.end(), [](Treap& x, Treap& y){return x.size() > y.size();});

        for(auto& tr : ret){
            if(tr.size() > v.size())
                swap(tr, v);
            // vの方が大きい
            int c = 0;
            while(tr.size()){
                auto val = tr.get(0);
                tr.pop_front();
                do{
                    if(c == v.size() || v.get(c) > val){
                        v.insert(c++, val);
                        break;
                    }
                }while(++c);
            }
        }

        /*
        while(1){
            int ind = -1;
            pair<int,int> mi(MOD + 5, MOD + 5);
            bool flag = true;
            for(int i = 0; i < ret.size(); ++i){
                auto& tr = ret[i];
                flag &= (tr.size() == 0);
                if(!que.empty() && mi > que.front()){
                    mi = que.front();
                    ind = i;
                }
            }
            if(flag)
                break;
            v.emplace_back(ret[ind].front());
            ret[ind].pop();
        }
        */

        v.push_front(make_pair(t1, t2));

        return v;
    };

    auto ret = f(0, n);
    for(int i = 0; i < n / 2; ++i)
        cout << ret.get(i).first + 1 << " " << ret.get(i).second + 1 << " \n"[i == n / 2 - 1];
        // cout << ret[i].first + 1 << " " << ret[i].second + 1 << " \n"[i == n / 2 - 1];

}


Measured memory_bytes: 51556