//----------------------------おまじない
#pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")
//----------------------------
#define FOR(i,j,n) for (int i=(j);i<(n);i++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define REPN(i,n) for (int i=(n);i>=0;i--)
#define I(n) scanf("%d", &(n))
#define LL(n) scanf("%lld", &(n))
#define pb(n) push_back((n))
#define mp(i,j) make_pair((i),(j))
#define eb(i,j) emplace_back((i),(j))
#include <bits/stdc++.h>
using namespace std;

//------------------------------typedef集
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
typedef vector<vi> vvi;
typedef vector<vpi> vvpi;
typedef vector<vvi> vvvi;
typedef long long ll;
const int mod = 1000000009;
struct SegmentTree {
private:
    int n;
    vector<int> node;

public:
    // 元配列 v をセグメント木で表現する
    SegmentTree(vi v) {
        // 最下段のノード数は元配列のサイズ以上になる最小の 2 冪 -> これを n とおく
        // セグメント木全体で必要なノード数は 2n-1 個である
        int sz = v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1, INT_MAX);

        // 最下段に値を入れたあとに、下の段から順番に値を入れる
        // 値を入れるには、自分の子の 2 値を参照すれば良い
        REP(i,sz) node[i+n-1] = v[i];
        REPN(i,n-2) node[i] = min(node[2*i+1], node[2*i+2]);
    }
    void update(int k, int x){
        k += n-1;
        node[k] = x;
        while(k){
            k = (k-1)/2;
            node[k] = min(node[2*k+1],node[2*k+2]);
        }
    }
    int getmin(int a, int b, int k=0, int l=0, int r=-1){
        if(r<0) r=n;
        if(r<=a || b<=l) return INT_MAX;
        if(a<=l && r<=b) return node[k];
        return min( getmin(a,b,2*k+1,l,(l+r)/2),getmin(a,b,2*k+2,(l+r)/2,r) );
    }
};

struct node{
public:
    int selfval,peerval;
    int left,A,B,right;

    bool operator<( const node& right ) const {
        return selfval < right.selfval;
    }
    bool operator>( const node& right ) const {
        return selfval > right.selfval;
    }

    node(int av, int bv, int l, int ai, int bi, int r):
        selfval(av), peerval(bv), left(l), A(ai), B(bi), right(r){}
    node():
        selfval(0), peerval(0), left(0), A(0), B(0), right(0){}
};

int n,a[200010],finv[200010];
vi even,odd;
priority_queue<node, vector<node>, greater<node>> nodepq;

node run(SegmentTree& ev, SegmentTree& od, int rangeleft, int rangeright){
    int A,B;
    if (rangeleft == rangeright) return node();
    if (!(rangeleft & 1)) {
        int lefteven = finv[ ev.getmin(rangeleft/2, rangeright/2) ];
        int rightodd = finv[ od.getmin(lefteven/2, rangeright/2)];
        A = lefteven;
        B = rightodd;
    } else {
        int leftodd = finv[ od.getmin(rangeleft/2, rangeright/2) ];
        int righteven = finv[ ev.getmin(leftodd/2+1, rangeright/2+1)];
        A = leftodd;
        B = righteven;
    }
    //int v1 = run(ev,od, mp(rangeleft,A));
    //int v2 = run(ev,od, mp(A+1,B));
    //int v3 = run(ev,od, mp(B+1,rangeright));

    return node(a[A],a[B],rangeleft,A,B,rangeright);
    //return A;
}

int main(){
    I(n);
    even.resize(n/2);
    odd.resize(n/2);
    REP(i,n) {
        I(a[i]); finv[a[i]] = i;
        if (i&1) { odd[i/2] = a[i]; }
            else { even[i/2] = a[i]; }
    }
    SegmentTree ev = SegmentTree(even);
    SegmentTree od = SegmentTree(odd);

    nodepq.push( run(ev,od,0,n) );
    while(!nodepq.empty()){
        node tgt = nodepq.top();
        nodepq.pop();
        if (tgt.selfval){
            printf("%d %d ", tgt.selfval, tgt.peerval);

            nodepq.push(run(ev,od,tgt.left,tgt.A));
            nodepq.push(run(ev,od,tgt.A+1,tgt.B));
            nodepq.push(run(ev,od,tgt.B+1,tgt.right));
        }
    }

    printf("\n");
}


Measured memory_bytes: 7028