//----------------------------おまじない
#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 val;
    int aval;
    int a,b,c;
    bool operator<( const node& right ) const {
        return aval < right.aval;
    }
    bool operator>( const node& right ) const {
        return aval > right.aval;
    }

    node(int v, int av, int ai, int bi, int ci):
        val(v), aval(av), a(ai), b(bi), c(ci){}
    node():
        val(0), aval(0), a(0), b(0), c(0){}
};

int n,a[200010],peer[200010],finv[200010];
vpi cut,nextcut;
int counter,reverse;
vi even,odd;
deque<int> dq;
priority_queue<node, vector<node>, greater<node>> nodepq;
vector<node> nodevec;

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

    nodevec[A] = node(A,a[A],v1,v2,v3);
    return A;
}

int main(){
    I(n);
    even.resize(n/2);
    odd.resize(n/2);
    nodevec.resize(n+1);
    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);
    int st = run(ev,od,mp(0,n));
    nodepq.push(nodevec[st]);
    while(!nodepq.empty()){
        node tgt = nodepq.top();
        nodepq.pop();
        dq.pb(tgt.val);
        dq.pb(peer[tgt.val]);
        if (tgt.a!=-1) nodepq.push(nodevec[tgt.a]);
        if (tgt.b!=-1) nodepq.push(nodevec[tgt.b]);
        if (tgt.c!=-1) nodepq.push(nodevec[tgt.c]);
        //cerr << tgt.a << " " << tgt.b << " " << tgt.c << endl;
    }


    for (auto i: dq) printf("%d ", a[i]);
    printf("\n");
}


Measured memory_bytes: 23928