#include <cmath>
#include <climits>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

struct RMQ{
	int n;
	vector<pair<int,int> > dat;

	RMQ(int n_){
		n = 1;
		while(n < n_) n *= 2;
		dat.resize(2*n-1);
		for(int i = 0;i < dat.size();i++) dat[i] = make_pair(INT_MAX,INT_MAX);
	}

	void update(int k,pair<int,int> a){
		k += n-1;
		dat[k] = a;
		while(k > 0){
			k = (k-1)/2;
			dat[k] = (dat[k*2+1]<dat[k*2+2])?dat[k*2+1]:dat[k*2+2];
		}
	}

	pair<int,int> query(int a,int b,int k,int l,int r){
		if(r <= a || b <= l) return make_pair(INT_MAX,INT_MAX);
		if(a <= l && r <= b) return dat[k];
		else{
			pair<int,int> vl = query(a,b,k*2+1,l,(l+r)/2);
			pair<int,int> vr = query(a,b,k*2+2,(l+r)/2,r);
			return (vl<vr)?vl:vr;
		}
	}
};

int main() {
    int n;
    cin >> n;
    vector<int> p(n);
    vector<int> q(n);
    for(int i = 0;i < n;i++) cin >> p[i];
    RMQ o(n/2),t(n/2);
    for(int i = 0;i < n/2;i++){
        o.update(i,make_pair(p[i*2],i*2));
        t.update(i,make_pair(p[i*2+1],i*2+1));
    }
    priority_queue<pair<pair<pair<int,int>,pair<int,int> >,pair<int,int> >,
    vector<pair<pair<pair<int,int>,pair<int,int> >,pair<int,int> > >,
    greater<pair<pair<pair<int,int>,pair<int,int> >,pair<int,int> > > > que;
    pair<int,int> p1,p2;
    p1 = o.query(0,n/2,0,0,o.n);
    p2 = t.query(p1.second/2,n/2,0,0,t.n);
    que.push(make_pair(make_pair(p1,p2),make_pair(0,n)));
    for(int i = 0;i < n/2;i++){
        pair<pair<pair<int,int>,pair<int,int> >,pair<int,int> > v = que.top();
        /*cout << '(' << v.first.first.first << ':' << v.first.first.second << ',' <<
                v.first.second.first << ':' << v.first.second.second << ')' << 
                ':' << v.second.first << ',' << v.second.second << endl;*/
        que.pop();
        q[i*2] = v.first.first.first;
        q[i*2+1] = v.first.second.first;
        int s,e;
        s = v.second.first;e = v.first.first.second;
        if(s < e){
            if(s%2){
                p1 = t.query(s/2,e/2,0,0,t.n);
                p2 = o.query(p1.second/2+1,e/2+1,0,0,o.n);
            }
            else{
                p1 = o.query(s/2,e/2,0,0,o.n);
                p2 = t.query(p1.second/2,e/2,0,0,t.n);
            }
            que.push(make_pair(make_pair(p1,p2),make_pair(s,e)));
        }
        s = v.first.first.second+1;e = v.first.second.second;
        if(s < e){
            if(s%2){
                p1 = t.query(s/2,e/2,0,0,t.n);
                p2 = o.query(p1.second/2+1,e/2+1,0,0,o.n);
            }
            else{
                p1 = o.query(s/2,e/2,0,0,o.n);
                p2 = t.query(p1.second/2,e/2,0,0,t.n);
            }
            que.push(make_pair(make_pair(p1,p2),make_pair(s,e)));
        }
        s = v.first.second.second+1;e = v.second.second;
        if(s < e){
            if(s%2){
                p1 = t.query(s/2,e/2,0,0,t.n);
                p2 = o.query(p1.second/2+1,e/2+1,0,0,o.n);
            }
            else{
                p1 = o.query(s/2,e/2,0,0,o.n);
                p2 = t.query(p1.second/2,e/2,0,0,t.n);
            }
            que.push(make_pair(make_pair(p1,p2),make_pair(s,e)));
        }
    }
    for(int i = 0;i < n;i++){
        cout << q[i] << " ";
    }cout << endl;
}

Measured memory_bytes: 8308