#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
#define ALL(v) v.begin(),v.end()
template < class T > inline bool chmax(T& a, T b) {if (a < b) { a=b; return true; } return false; }
template < class T > inline bool chmin(T& a, T b) {if (a > b) { a=b; return true; } return false; }
#define DEBUG_VLL(vec) REP(sz, vec.size()) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

template < class T >
class SegmentTree {
    // 0-indexed Segment Tree
    long long n; // 葉の数
    vector<T> data;  // データを格納する配列
    T def;  // 初期値（単位元）
    function<T(T, T)> operation;  // 区間クエリで使う処理
    function<T(T, T)> update;  // 点更新で使う処理

    // 区間 [a, b) に対する query !!!!!
    T _query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return def;
        if (a <= l && r <= b) return data[k];  // a,l,r,bの順で含まれる
        else {
            T c1 = _query(a, b, 2*k+1, l, (l+r)>>1);
            T c2 = _query(a, b, 2*k+2, (l+r)>>1, r);
            return operation(c1, c2);
        }
    }

public:
    // _n: 葉の要素の数, _def: 初期値（単位元）, _operation: クエリの関数, _update: 更新用の関数
    SegmentTree(size_t _n, T _def, function<T(T, T)> _operation, function<T(T, T)> _update)
        : n(_n), def(_def), operation(_operation), update(_update) {
            n = 1;
            while (n < _n) n<<=1;
            data = vector<T>(2*n-1, def);
        }
    
    void change(int i, T x) {
        i += n - 1;
        data[i] = update(data[i], x);
        while (i>0) {
            i = (i-1)>>1;
            data[i] = operation(data[i*2+1], data[i*2+2]);
        }
    }

    // 区間 [a, b) に対する query !!!!!
    T query(int a, int b) {
        return _query(a, b, 0, 0, n);
    }

    T operator[](int i) {
        return data[i+n-1];
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    V<int> p(n);
    for (int i = 0; i < n; i++) cin >> p[i];
    SegmentTree< P<int, int> > oddseg(n, make_pair(INF, -1),  // 奇数の最小値
        [&](P<int, int> i, P<int, int> j) {
            return min(i, j);
        },
        [&](P<int, int> i, P<int, int> j) {
            return min(i, j);
        }),
        evenseg(n, make_pair(INF, -1),  // 偶数の最小値
        [&](P<int, int> i, P<int, int> j) {
            return min(i, j);
        },
        [&](P<int, int> i, P<int, int> j) {
            return min(i, j);
        });
    
    for (int i = 0; i < n; i++) {
        if (i & 1) oddseg.change(i, make_pair(p[i], i));
        else evenseg.change(i, make_pair(p[i], i));
    }

    V<int> ans;
    // auto c = [&](P<int, int> l, P<int, int> r) {
    //     return (l.first & 1 ? oddseg : evenseg).query(l.first, l.second).first < (r.first & 1 ? oddseg : evenseg).query(r.first, r.second).first;
    // };
    // pq には半開区間 [l, r) を入れる
    priority_queue< P< P<int, int>, P<int, int> >, V< P< P<int, int>, P<int, int> > >, greater< P< P<int, int>, P<int, int> > > > pq;
    pq.push( make_pair(evenseg.query(0, n), make_pair(0, n) ) );
    while (!pq.empty()) {
        P< P<int, int>, P<int, int> > seg = pq.top(); pq.pop();
        P<int, int> q1 = seg.first;
        ans.emplace_back(q1.first);
        P<int, int> q2 = (seg.second.first & 1 ? evenseg : oddseg).query(q1.second + 1, seg.second.second);
        ans.emplace_back(q2.first);
        if (seg.second.first < q1.second - 1) pq.push( make_pair(
            (seg.second.first & 1 ? oddseg : evenseg).query(seg.second.first, q1.second), make_pair(seg.second.first, q1.second) ) );
        if (q1.second + 1 < q2.second - 1) pq.push( make_pair(
            ((q1.second + 1) & 1 ? oddseg : evenseg).query(q1.second + 1, q2.second) , make_pair(q1.second + 1, q2.second) ) );
        if (q2.second + 1 < seg.second.second - 1) pq.push( make_pair(
            ((q2.second + 1) & 1 ? oddseg : evenseg).query(q2.second + 1, seg.second.second), make_pair(q2.second + 1, seg.second.second) ) );
    }
    for (int i = 0; i < n; i++) cout << ans[i] << '\n';
    return 0;
}


Measured memory_bytes: 14300