#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define rep(i,l,r) for(int i=(l);i<(r);++i)
#define dd(x) cout << #x << " = " << x << ", "
#define de(x) cout << #x << " = " << x << endl
//-------
const int N = 2e5 + 7;
const int INF = 1e9 + 7;
int n, a[N], p[N];
struct SegTree {
	#define ls ((t)<<1)
	#define rs ((t)<<1|1)
	bool rev[N << 2], st[N << 2];
	int val[2][N << 2];
	void up(int t) {
		val[0][t] = min(val[0][ls], val[0][rs]);
		val[1][t] = min(val[1][ls], val[1][rs]);
	}
	void down(int t) {
		if (rev[t]) {
			rev[ls] ^= 1, st[ls] ^= 1, swap(val[0][ls], val[1][ls]);
			rev[rs] ^= 1, st[rs] ^= 1, swap(val[0][rs], val[1][rs]);
			rev[t] = 0;
		}
	}
	void build(int t, int l, int r) {
		rev[t] = false;
		if (l == r) {
			val[0][t] = val[1][t] = INF;
			st[t] = l & 1, val[l & 1][t] = a[l];
		} else {
			int z = (l + r) >> 1;
			build(ls, l, z), build(rs, z + 1, r);
			up(t);
		}
	}
	void upd(int t, int l, int r, int L, int R) {
		if (L <= l && r <= R) {
			rev[t] ^= 1, st[t] ^= 1, swap(val[0][t], val[1][t]);
			return ;
		}
		down(t);
		int z = (l + r) >> 1;
		if (L <= z) upd(ls, l, z, L, R);
		if (R > z) upd(rs, z + 1, r, L, R);
		up(t);
	}
	void updval(int t, int l, int r, int P, int V) {
		if (l == r) {
			val[0][t] = val[1][t] = INF;
			val[st[t]][t] = V;
			return ;
		}
		down(t);
		int z = (l + r) >> 1;
		if (P <= z) updval(ls, l, z, P, V);
		else updval(rs, z + 1, r, P, V);
		up(t);
	}
	int qry(int t, int l, int r, int L, int R, int x) {
		if (L <= l && r <= R) return val[x][t];
		down(t);
		int z = (l + r) >> 1, ret = INF;
		if (L <= z) ret = min(ret, qry(ls, l, z, L, R, x));
		if (R > z) ret = min(ret, qry(rs, z + 1, r, L, R, x));
		up(t);
		return ret;
	}
	int qryst(int t, int l, int r, int P) {
		if (l == r) return st[t];
		down(t);
		int z = (l + r) >> 1, ret;
		if (P <= z) ret = qryst(ls, l, z, P);
		else ret = qryst(rs, z + 1, r, P);
		up(t);
		return ret;
	}
	int qrymin(int t, int l, int r, int L, int R) {
		if (L > R) return INF;
		if (L <= l && r <= R) return min(val[0][t], val[1][t]);
		down(t);
		int z = (l + r) >> 1, ret = INF;
		if (L <= z) ret = min(ret, qrymin(ls, l, z, L, R));	
		if (R > z) ret = min(ret, qrymin(rs, z + 1, r, L, R));
		up(t);
		return ret;
	}
} seg;
pair<int, int> get(int l, int r) {
	if (l >= r) return mp(-INF, -INF);
	pair<int, int> ret = mp(-INF, -INF);
	rep(i, 0, 2) {
		int x = seg.qry(1, 1, n, l, r, i), y;
		if (i & 1) {
			y = seg.qry(1, 1, n, p[x] + 1, r, 0);
			ret = max(ret, mp(-x, -y));
		} else {
			y = seg.qry(1, 1, n, l, p[x] - 1, 1);
			ret = max(ret, mp(-y, -x));
		}
	}
	return ret;
}
void bfs() {
	priority_queue<pair<pair<int, int>, pair<int, int> > > que;
	que.push(mp(get(1, n), mp(1, n)));
	while (!que.empty()) {
		pair<int, int> now = que.top().fi;
		int l = que.top().se.fi;
		int r = que.top().se.se;
		que.pop();
		if (abs(now.fi) >= INF) continue;
		int x = -now.fi, y = -now.se;
		printf("%d %d ", x, y);
		seg.updval(1, 1, n, p[x], INF);	
		seg.updval(1, 1, n, p[y], INF);	
		seg.upd(1, 1, n, p[x], n);
		seg.upd(1, 1, n, p[y], n);	
		if (p[x] > p[y]) swap(x, y);
		que.push(mp(get(l, p[x] - 1), mp(l, p[x] - 1)));	
		que.push(mp(get(p[x] + 1, p[y] - 1), mp(p[x] + 1, p[y] - 1)));
		que.push(mp(get(p[y] + 1, r), mp(p[y] + 1, r)));
	}
}
int main() {
	scanf("%d", &n);
	rep(i, 1, n + 1) scanf("%d", a + i), p[a[i]] = i;
	seg.build(1, 1, n);
	bfs();
	return 0;
}

Measured memory_bytes: 16112