//
//  main.cpp
//

#include <algorithm>
#include <array>
#include <assert.h>
#include <iostream>
#include <limits>
#include <math.h>
#include <memory>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = long long;
using ull = unsigned long long;

template<typename Monoid>
struct SegmentTree {
    using Op = function<Monoid(const Monoid& lhs, const Monoid& rhs)>;
    size_t width;
    vector<Monoid> node;
    Op op;
    Monoid unit;
    
    SegmentTree(const vector<Monoid>& elems, Op op, Monoid unit)
    : op(op)
    , unit(unit) {
        width = 1;
        while (width < elems.size()) {
            width *= 2;
        }
        node.resize(2 * width - 1, unit);
        for (size_t i = 0; i < elems.size(); i++) {
            node[i + width - 1] = elems[i];
        }
        for (size_t i = width - 2; i != numeric_limits<size_t>::max(); i--) {
            node[i] = op(node[2 * i + 1], node[2 * i + 2]);
        }
    }
    void update(size_t idx, Monoid elem) {
        idx += width - 1;
        node[idx] = elem;
        while (idx >= 1) {
            idx = (idx - 1) / 2;
            node[idx] = op(node[2 * idx + 1], node[2 * idx + 2]);
        }
    }
    Monoid query(size_t a, size_t b, size_t root) const {
        assert(0 <= a && b <= width);
        size_t left = root, right = root;
        while (left < width - 1) {
            left = 2 * left + 1;
        }
        left -= (width - 1);
        while (right < width - 1) {
            right = 2 * right + 2;
        }
        right -= (width - 1);
        right++;
        if (right <= a || b <= left) {
            return unit;
        }
        if (a <= left && right <= b) {
            return node[root];
        }
        Monoid ans_l = query(a, b, 2 * root + 1);
        Monoid ans_r = query(a, b, 2 * root + 2);
        return op(ans_l, ans_r);
    }
};

int main() {
//    vector<int> TEST_xs;
//    int TEST_N = 4;
//    for (int i = 0; i < TEST_N; i++) {
//        TEST_xs.push_back(i+1);
//    }
//    do {
//        cout << TEST_N << endl;
//        for (int i = 0; i < TEST_N; i++) {
//            cout << TEST_xs[i];
//            if (i < TEST_N - 1) {
//                cout << " ";
//
//            }
//        }
//        cout << endl;
//    } while (next_permutation(TEST_xs.begin(), TEST_xs.end()));
//    return 0;
//
    int N;
    cin >> N;
    const int UNIT = numeric_limits<int>::max();
    unordered_map<int, int> val_to_idx;
    vector<int> Pis;
    vector<int> Pis_even;
    vector<int> Pis_odd;
    for (int i = 0; i < N; i++) {
        int Pi;
        cin >> Pi;
        Pis.push_back(Pi);
        if (i % 2 == 0) {
            Pis_even.push_back(Pi);
            Pis_odd.push_back(UNIT);
        } else {
            Pis_even.push_back(UNIT);
            Pis_odd.push_back(Pi);
        }
        val_to_idx[Pi] = i;
    }
    SegmentTree<int> tree_even(Pis_even, [](int lhs, int rhs){ return min(lhs, rhs); }, UNIT);
    SegmentTree<int> tree_odd(Pis_odd, [](int lhs, int rhs){ return min(lhs, rhs); }, UNIT);
    struct Range {
        int start;
        int end;
        int left;
        int right;
    };
    auto select_tree = [&tree_odd, &tree_even](int idx) -> const SegmentTree<int>& {
        return (idx % 2 == 0) ? tree_even : tree_odd;
    };
    auto make_range = [&val_to_idx, &select_tree](int start, int end) -> Range {
        int left = val_to_idx[select_tree(start).query(start, end, 0)];
        int right = val_to_idx[select_tree(start+1).query(left+1, end, 0)];
        return {start, end, left, right};
    };
    auto compare = [&Pis](Range lhs, Range rhs) {
        return !(Pis[lhs.left] < Pis[rhs.left] || (Pis[lhs.left] == Pis[rhs.left] && Pis[lhs.right] < Pis[rhs.right]));
    };
    priority_queue<Range, vector<Range>, decltype(compare)> queue(compare);
    queue.push(make_range(0, N));
    vector<int> ans;
    while (!queue.empty()) {
        Range range = queue.top();
        queue.pop();
        ans.push_back(Pis[range.left]);
        ans.push_back(Pis[range.right]);
        if (range.start < range.left) {
            queue.push(make_range(range.start, range.left));
        }
        if (range.left + 1 < range.right) {
            queue.push(make_range(range.left + 1, range.right));
        }
        if (range.right + 1 < range.end) {
            queue.push(make_range(range.right + 1, range.end));
        }
    }
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i];
        if (i < ans.size() - 1) {
            cout << " ";
        }
    }
    cout << endl;
}


Measured memory_bytes: 18636