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

const int MAXN = 500000;
const int INF = 1e9;
int a[MAXN], pos[MAXN], ans[MAXN], n;

struct Segment {
	int sum, mn[2];
} tr[MAXN];

inline int get_node(int l, int r) {
	return (l + r) | (l != r);
}

inline void update(int k, int l, int r) {
	int mid = (l + r) >> 1,
		lc = get_node(l, mid),
		rc = get_node(mid + 1, r);
	tr[k].sum = tr[lc].sum + tr[rc].sum;
	tr[k].mn[0] = min(tr[lc].mn[0], tr[rc].mn[tr[lc].sum & 1]);
	tr[k].mn[1] = min(tr[lc].mn[1], tr[rc].mn[(tr[lc].sum & 1) ^ 1]);
}

inline void build_tree(int l, int r) {
	int k = get_node(l, r);
	tr[k].sum = r - l + 1;
	if (l == r) {
		tr[k].mn[0] = INF;
		tr[k].mn[1] = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build_tree(l, mid);
	build_tree(mid + 1, r);
	update(k, l, r);
}

inline void del(int l, int r, int x) {
	int k = get_node(l, r);
	if (l == r) {
		tr[k].sum = 0;
		tr[k].mn[0] = tr[k].mn[1] = INF;
		return;
	}
	int mid = (l + r) >> 1;
	if (x > mid) {
		del(mid + 1, r, x);
	} else {
		del(l, mid, x);
	}
	update(k, l, r);
}

int flag = 0;

inline void query(int l, int r, int a, int b, int &s, int &x) {
	int k = get_node(l, r);
/*if (1) {
	cout << "query: " << l << " " << r << " " << a << " " << b << " " << s << " " << x << endl;
	cout << "info: " << tr[k].sum << " " << tr[k].mn[0] << " " << tr[k].mn[1] << endl;
}*/
	if (l == a && r == b) {
		x = min(x, tr[k].mn[s]);
		s ^= tr[k].sum & 1;
		return;
	}
	int mid = (l + r) >> 1;
	if (a > mid) {
		query(mid + 1, r, a, b, s, x);
		return;
	}
	if (b <= mid) {
		query(l, mid, a, b, s, x);
		return;
	}
	query(l, mid, a, mid, s, x);
	query(mid + 1, r, mid + 1, b, s, x);
}
/*
inline int query_sum(int l, int r, int a, int b) {
	int k = get_node(l, r);
	if (l == a && r == b) {
		return tr[k].sum;
	}
	int mid = (l + r) >> 1;
	if (a > mid) {
		return query_sum(mid + 1, r, a, b);
	}
	if (b <= mid) {
		return query_sum(l, mid, a, b);
	}
	return query_sum(l, mid, a, mid) + query_sum(mid + 1, r, mid + 1, b);
}*/

set<int> S;

struct Element {
	int x, y, l, r;
	Element() {};
	Element(int _x, int _y, int _l, int _r): x(_x), y(_y), l(_l), r(_r) {};
};

inline bool operator < (const Element &p, const Element &q) {
	return p.x != q.x ? p.x < q.x : p.y < q.y;
}

set<Element> seg;

set<int> chosen;

inline void get_segment(int l, int r, int &x, int &y) {
	if (l == r + 1) {
		return;
	}
	x = y = INF;
	set<int>::iterator it = S.upper_bound(r);
	--it;
	--it;
//cerr << l << " " << *it << endl;
	int s = 1;
	query(1, n, l, *it, s, x);
//cerr << x << endl;
//return;
	del(1, n, pos[x]);
	s = 1;
	query(1, n, pos[x], r, s, y);
	del(1, n, pos[y]);
	seg.insert(Element(x, y, l, r));
	chosen.insert(pos[x]);
	chosen.insert(pos[y]);
}

int main() {
	scanf("%d", &n);
	S.clear();
	chosen.clear();
	chosen.insert(0);
	chosen.insert(n + 1);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		pos[a[i]] = i;
		S.insert(i);
	}
	S.insert(n + 1);
	
	build_tree(1, n);
	int x, y;
	seg.clear();
	get_segment(1, n, x, y);
	//return 0;
	
	int cnt = 0;
	for (int i = 0; i < n / 2; ++i) {
		Element now = *(seg.begin());
		seg.erase(seg.begin());
		ans[++cnt] = now.x;
		ans[++cnt] = now.y;
		int x = pos[now.x], y = pos[now.y], tx, ty;
		set<int>::iterator it = chosen.lower_bound(x);
		--it;
		get_segment((*it) + 1, x - 1, tx, ty);
		get_segment(x + 1, y - 1, tx, ty);
		it = chosen.lower_bound(y);
		++it;
		get_segment(y + 1, (*it) - 1, tx, ty);
	}
	
	for (int i = 1; i < n; ++i) {
		printf("%d ", ans[i]);
	}
	cout << ans[n] << endl;
}

Measured memory_bytes: 32512