#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma warning(disable : 4996)
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include<random>
#include<array>


using namespace std;

#define REP(i, n) for(int i = 0;i < n;++i)
#define REPR(i, n) for(int i = n-1;i >= 0;--i)
#define FOR(i, m, n) for(int i = m;i < n;++i)
#define FORR(i, m, n) for(int i = m-1;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout<<(x)<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define lb(v,n) lower_bound(v.begin(), v.end(), (n))
#define ub(v,n) upper_bound(v.begin(), v.end(), (n))
#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
typedef pair<int, int>P;
std::random_device rd;
std::mt19937 mt(rd());
constexpr int MOD = 1e9+7; constexpr int MAX = 200020;
const double pi = acos(-1); constexpr double EPS = 1e-8;
constexpr ll INF = 1e16;


template<typename T>
struct SegmentTree {
	int n;
	T unit;
	vector<T>dat;
	function<T(T, T)> func;
	SegmentTree(const int N, T _unit, function<T(T, T)> _func)
		:unit(_unit), func(_func) {
		n = 1;
		//簡単のため、要素数を2のべき乗に
		while (n < N)n *= 2;
		dat.assign(2 * n, unit);
	}

	void update(int k, T a) {
		k += n - 1;//葉の節点
		dat[k] = a;
		//上りながら更新
		while (k > 0) {
			k = (k - 1) / 2;
			dat[k] = func(dat[k * 2 + 1], dat[k * 2 + 2]);
		}
	}
	T _query(int a, int b, int k, int l, int r) {
		//[a,b)と[l,r)が交差していなければ、funcに影響を与えない値を返す
		if (r <= a || b <= l)return unit;
		//[a,b)が[l,r)を完全に含んでいれば、この節点の値
		if (a <= l && r <= b)return dat[k];
		else {
			T vl = _query(a, b, k * 2 + 1, l, (l + r) / 2);
			T vr = _query(a, b, k * 2 + 2, (l + r) / 2, r);
			return func(vl, vr);
		}
	}
	//[a,b)
	T query(int a, int b) {
		return _query(a, b, 0, 0, n);
	}
};
//auto f = [](int a, int b) {return a + b; };
//SegmentTree<int>seg(N,0,f);

vector<P> calc(int l, int r,SegmentTree<P>&even,SegmentTree<P>&odd) {
	//pe(l); print(r);
	int k1 = l, k2 = r - 1;
	vector<P>ret;
	if (l + 1 >= r)return ret;
	if (l % 2 == 0) {
		P fi = even.query(l, r);
		k1 = fi.second;
		P se = odd.query(k1, r);
		k2 = se.second;
		ret.push_back({ fi.first,se.first });
	}
	else {
		P fi = odd.query(l, r);
		k1 = fi.second;
		P se = even.query(k1, r);
		k2 = se.second;
		ret.push_back({ fi.first,se.first });
	}
	vector<P>v1 = calc(l, k1,even,odd);
	vector<P>v2 = calc(k1 + 1, k2, even, odd);
	vector<P>v3 = calc(k2 + 1, r,even,odd);
	v1.push_back({ 1e9,1e9 });
	v2.push_back({ 1e9,1e9 });
	v3.push_back({ 1e9,1e9 });
	VREVERSE(v1); VREVERSE(v2); VREVERSE(v3);
	while (true) {
		if (v1.back() < v2.back()&&v1.back() < v3.back()) {
			P res = v1.back();
			if (res.first == 1e9)break;
			ret.push_back(res);
			v1.pop_back();
		}
		else if (v2.back() < v3.back()&&v2.back()< v1.back()) {
			P res = v2.back();
			if (res.first == 1e9)break;
			ret.push_back(res);
			v2.pop_back();
		}
		else {
			P res = v3.back();
			if (res.first == 1e9)break;
			ret.push_back(res);
			v3.pop_back();
		}
	}
	return ret;
}
typedef array<int, 3> arr;
void solve() {
	int N; cin >> N;
	auto f = [](P a, P b) {return min(a,b); };
	SegmentTree<P>even(N, { 1e9,1e9 }, f), odd(N, { 1e9,1e9 }, f);
	vector<int>v(N);
	REP(i, N) {
		cin >> v[i];
		if (i & 1) {
			odd.update(i, { v[i],i });
		}
		else {
			even.update(i, { v[i],i });
		}
	}
	priority_queue < array<int, 3>, vector < array<int, 3>>,greater<array<int, 3>>>que;
	que.push({ 1,0,N });
	vector<int>ans;
	while (!que.empty()) {
		arr ar = que.top(); que.pop();
		int l = ar[1], r = ar[2];
		if (l + 1 >= r)continue;
		int k1 = l, k2 = r - 1;
		if (l % 2 == 0) {
			P fi = even.query(l, r);
			k1 = fi.second;
			P se = odd.query(k1, r);
			k2 = se.second;
			ans.push_back(fi.first); ans.push_back(se.first);
		}
		else {
			P fi = odd.query(l, r);
			k1 = fi.second;
			P se = even.query(k1, r);
			k2 = se.second;
			ans.push_back(fi.first); ans.push_back(se.first);
		}
		if (k1 > l + 1) {
			int nxt = 1e9;
			if (l % 2 == 0)nxt = even.query(l, k1).first;
			else nxt = odd.query(l, k1).first;
			que.push({ nxt,l,k1 });
		}
		if (k2 > k1 + 1 + 1) {
			int nxt = 1e9;
			if ((k1 + 1) % 2 == 0)nxt = even.query(k1 + 1, k2).first;
			else nxt = odd.query(k1 + 1, k2).first;
			que.push({ nxt,k1 + 1,k2 });
		}
		if (r > k2 + 1 + 1) {
			int nxt = 1e9;
			if ((k2 + 1) % 2 == 0)nxt = even.query(k2 + 1, r).first;
			else nxt = odd.query(k2 + 1, r).first;
			que.push({ nxt,k2 + 1,r });
		}
	}
	print_space(ans);
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//int q; cin >> q;
	//while (q--)
	solve();
}



Measured memory_bytes: 22304