#include <bits/stdc++.h>

using namespace std;

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)

using ll = long long;
using P = std::tuple<int,int>;
using P3 = std::tuple<int,int,int>;
    
const int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1}, dy[8] = {0, 0, -1, 1, -1, 1, -1, 1};

// I want to delete this stupid solution ;(
#define sandwich(x) [](auto a, auto b){return (x)(a, b);}

template <typename T>
using F2 = std::function<T(T,T)>;

template <typename T, int N, typename F = std::plus<T> >
struct SegmentTree{
    SegmentTree(T u, F f = F()){
        size = 1;
        while(size < N){
            size <<= 1;
        }

        unit = u;
        func = f;

        init();
    }
    void addParentIndex(int parent){
        index[parent] = data[parent] == data[parent*2] ? index[parent*2] : index[parent*2+1];
    }
    void init(){
        for(int i=0;i<size;++i){
            data[i+size] = unit;
            index[i+size] = i;
        }

        for(int i=size-1;i>0;--i){
            data[i] = func(data[i*2], data[i*2+1]);
            addParentIndex(i);
        }
    }
    void update(int k, int v){
        k += size;
        data[k] = v;

        while(k > 1){
            k >>= 1;
            data[k] = func(data[k*2], data[k*2+1]);
            addParentIndex(k);
        }
    }
    inline std::tuple<T, int> query(int l, int r){
        return _query(l, r, 1, 0, size);
    }
    std::tuple<T, int> _query(int a, int b, int k, int l, int r){
        if(b <= l || r <= a){return std::make_tuple(unit, -1);}
        if(a <= l && r <= b){return std::make_tuple(data[k], index[k]);}
        int mid = (l + r) >> 1;
        auto ql = _query(a, b,   2*k,   l, mid),
             qr = _query(a, b, 2*k+1, mid, r  );
        auto res = func(fst(ql), fst(qr));
        return std::make_tuple(res, res == fst(ql) ? snd(ql) : snd(qr));
    }

    T unit, data[N*4];
    int index[N*4];
    int size;
    F func;
};

SegmentTree<ll, 200200, F2<ll>> segtree[2] = {{252521, sandwich(std::min)}, {252521, sandwich(std::min)}};
std::priority_queue<P3, std::vector<P3>, std::greater<P3>> pq;
std::vector<int> res;

int minimumLeft(int l, int r){
    int re = l & 1;

    int a;
    tie(a, ignore) = segtree[re].query(l, r + 1);
    
    return a;
}

inline bool isValid(int l, int r){return l <= r;}

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

    int N;
    std::cin >> N;

    for(int i=0;i<N;++i){
        int p;
        std::cin >> p;
        
        int r = i & 1;
        segtree[r].update(i, p);
    }

    pq.emplace(minimumLeft(0, N-1), 0, N - 1);

    while(!pq.empty()){
        int a, l, r;
        tie(a, l, r) = pq.top();
        pq.pop();

        int re = l & 1;
        int ia, b, ib;
        tie(ignore, ia) = segtree[re].query(l, r + 1);
        tie(b, ib) = segtree[!re].query(ia, r + 1);

        res.emplace_back(a);
        res.emplace_back(b);

        if(isValid(l, ia - 1)){
            pq.emplace(minimumLeft(l, ia - 1), l, ia - 1);
        }
        if(isValid(ia + 1, ib - 1)){
            pq.emplace(minimumLeft(ia + 1, ib - 1), ia + 1, ib - 1);
        }
        if(isValid(ib + 1, r)){
            pq.emplace(minimumLeft(ib + 1, r), ib + 1, r);
        }
    }

    for(int i=0;i<N;++i){
        std::cout << res[i] << " \n"[i+1==N];
    }
}

Measured memory_bytes: 21388