//E
#include<bits/stdc++.h>
using namespace std;


#define MAX 200002

int n;

struct st{
	int cnt;
	pair<int, int> mint;
	st *lef;
	st *rig;
	pair<int, int> val;
	int L;
	int R;
	st(){
		cnt = 0;
		mint = make_pair(INT_MAX, INT_MAX);
		val = make_pair(INT_MAX, INT_MAX);
		lef = rig = NULL;
	}
	void upd(){
		cnt = 0;
		mint = val;
		if (val.first != INT_MAX){
			cnt = 1;
		}
		if (lef != NULL){
			mint = min(mint, lef->mint);
			cnt += lef->cnt;
		}
		if (rig != NULL){
			mint = min(mint, rig->mint);
			cnt += rig->cnt;
		}
	}
};
st linkk[MAX * 4];

st *root[2];

int ord;
st *neww(){
	ord++;
	if (ord >= MAX * 4){
		return new st();
	}
	return &linkk[ord - 1];
}
inline st* add(st *&b, int l, int r, int ll,int x){
	if (ll < l || r <= ll){
		return b;
	}
	if (b == NULL){
		b = neww();
		b->L = l;
		b->R = r;
	}
	if (l + 1 == r){
		b->cnt = 1;
		b->val = make_pair(x, l);
		b->upd();
		return b;
	}
	add(b->lef, l, (l + r) >> 1,ll,x);
	add(b->rig, (l + r) >> 1, r, ll, x);
	b->upd();
}
inline void er(st *&b, int ll){
	if (b == NULL){
		return;
	}
	
	int l = b->L;
	int r = b->R;
	if (l <= ll&&ll < r){

	}
	else{
		return;
	}
	if (l + 1 == r){
		b->cnt = 0;
		b->val = make_pair(INT_MAX,INT_MAX);
		b->upd();
		return;
	}
	er(b->lef, ll);
	er(b->rig, ll);
	b->upd();
}

priority_queue<pair<pair<int,int>, pair<int,int> > ,vector<pair<pair<int,int>,pair<int,int> > > ,greater<pair<pair<int,int>,pair<int,int> > > > q;

inline pair<int, int> query(st *&b, int ll,int rr){
	if (b == NULL){
		return make_pair(INT_MAX, INT_MAX);
	}
	int l = b->L;
	int r = b->R;
	if (ll <= l&&r <= rr){
		return b->mint;
	}
	if (rr <= l || r <= ll){
		return make_pair(INT_MAX, INT_MAX);
	}
	return min(query(b->lef, ll,rr), query(b->rig, ll,rr) );
}

vector<int> ans;
set<int> s;

struct BIT{
	vector<int> bit;
	void resize(int N){
		bit.assign(N, 0);
	}
	void add(int i, int j){
		i++;
		while (i < bit.size()){
			bit[i] += j;
			i += i&-i;
		}
	}
	int sum(int i){
		int r = 0;
		i++;
		while (i){
			r += bit[i];
			i -= i&-i;
		}
		return r;
	}
	int rng(int lef, int rig){
		int F = sum(rig);
		if (lef){
			F -= sum(lef - 1);
		}
		return F;
	}
};
BIT  b;
int par(int x){
	return b.sum(x) % 2;
}
int main(){
	cin >> n;
	b.resize(n);
	root[0] = NULL;
	root[1] = NULL;
	for (int i = 0; i < n; i++){
		int p;
		scanf("%d", &p);
		add(root[i & 1], 0, n, i, p);
	}
	q.push(make_pair(root[0]->mint, make_pair(0,n) ) );
	s.insert(n);
	while (!q.empty()){
		pair<int, int> f = q.top().second;
		int val = q.top().first.first;
		int idx = q.top().first.second;
		q.pop();
		ans.push_back(val);
		int p = par(idx);
		auto ff = query(root[1^p], idx,(*s.lower_bound(idx)) );
		s.insert(idx);
		s.insert(ff.second);
		b.add(idx, 1);
		b.add(ff.second, 1);
		ans.push_back(ff.first);
		er(root[p^1], ff.second);
		er(root[p], idx);
		int ar[] = { f.first-1, idx, ff.second, f.second };
		for (int i = 0; i < 3; i++){
			if (ar[i]+1 < ar[i + 1]){
				auto ff = query(root[p], ar[i] + 1, ar[i + 1]);
				if (ff.first != INT_MAX){
					q.push(make_pair(ff,make_pair(ar[i] + 1, ar[i + 1])));
				}
			}
			p ^= 1;
		}
	}
	for (int i = 0; i < ans.size(); i++){
		if (i)printf(" ");
		printf("%d", ans[i]);
	}
	puts("");
	return 0;
}

Measured memory_bytes: 50548