#include <stdio.h>
#include <assert.h>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <limits>
#include <array>
#include <vector>
#include <queue>
#include <set>
#include <map>
//#include <unordered_map>
//#include <unordered_set>
//#include <boost/container/static_vector.hpp>
//#include <boost/unordered_set.hpp>
//#include <boost/unordered_map.hpp>
//#include <unistd.h>

//#include <cv.h>
//#include <highgui.h>
#include <stdlib.h>
#include <string>

class RMQ {
    // Range Minimum Query : 数列要素1つの変更、ある区間の最小値を求める操作を実現
    public:
    int n;
    std::vector<long long> data;
    long long LIMIT;
    RMQ() {}
    RMQ(const int size) {
        // 要素数を2のべき乗にする。
        LIMIT = std::numeric_limits<long long>::max();
        n = 1;
        while (n < size) {
            n *= 2;
        }
        data.resize(n*2, LIMIT);
    }

    void update(int k, int a) {
        k += n - 1; // データ配列k番目は、セグメント木配列のn-1+k番目に対応。
        data[k] = a;

        while (k > 0) {
            k = (k - 1) / 2; // セグメント木配列k番目の親が(k-1)/2
            data[k] = std::min(data[k*2+1], data[k*2+2]); // kの子2つ
        }
    }

    // データ配列の区間[a,b]の最小値を求める。query_childと異なり閉区間
    long long query(const int a, const int b) {
        return query_child(a, b+1, 0, 0, n);
    }

    // データ配列の区間[a,b)の最小値を求める。
    // k:探索しているセグメント木の節点のセグメント木配列番号
    // [l, r):kに対応する区間
    long long query_child(const int a, const int b, const int k, const int l, const int r) {
        if (r <= a || b <= l) { return LIMIT; }
        if (a <= l && r <= b) { return data[k]; }

        long long vl = query_child(a, b, k*2 + 1, l, (l+r)/2);
        long long vr = query_child(a, b, k*2 + 2, (l+r)/2, r);
        return std::min(vl, vr);
    }
};

const int MAX_N = 200050;
int N;
int p[MAX_N];
int loc[MAX_N];

RMQ rmq_odd = RMQ(MAX_N);
RMQ rmq_even = RMQ(MAX_N);

std::vector<std::pair<int, int>> ret;

int cal_priority(const std::pair<int, int>& range) {
    if (range.second - range.first == -1) {
        return N * 2;
    }
    assert(0 <= range.second - range.first);
    assert((range.second - range.first) % 2 != 0);
    return (range.first % 2 == 1) ? rmq_odd.query(range.first, range.second) : rmq_even.query(range.first, range.second);
}

std::pair<int, int> get_pair(int begin, int end) {
    assert((end - begin) % 2 != 0);

    int first = (begin % 2 == 1) ? rmq_odd.query(begin, end) : rmq_even.query(begin, end);
    int second = (begin % 2 == 1) ? rmq_even.query(loc[first], end) : rmq_odd.query(loc[first], end);
    return std::pair<int, int>({first, second});
}

int main(int argc, char **argv) {
    std::cin >> N;

    for (int i = 1; i <= N; i++) {
        std::cin >> p[i];
    }

    for (int i = 1; i <= N; i++) {
        loc[p[i]] = i;
    }

    for (int i = 1; i <= N; i++) {
        if (i % 2 == 0) {
            rmq_even.update(i, p[i]);
        } else {
            rmq_odd.update(i, p[i]);
        }
    }

    std::vector<int> ret;
    auto comp = [](const std::pair<int, int>& lhs, const std::pair<int, int>& rhs) {
        return cal_priority(lhs) > cal_priority(rhs);
    };
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, decltype(comp)> que(comp);
    que.push(std::pair<int, int>({1, N}));

    while (!que.empty()) {
        std::pair<int, int> range = que.top(); que.pop();

        if (cal_priority(range) <= N) {
            std::pair<int, int> vp = get_pair(range.first, range.second);
            ret.push_back(vp.first);
            ret.push_back(vp.second);

            que.push(std::pair<int, int>({range.first, loc[vp.first] - 1}));
            que.push(std::pair<int, int>({loc[vp.first] + 1, loc[vp.second] - 1}));
            que.push(std::pair<int, int>({loc[vp.second] + 1, range.second}));
        }
    }

    for (int i : ret) {
        std::cout << i << " ";
    }
    std::cout << std::endl;
    return 0;
}


Measured memory_bytes: 14832