#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
#include<time.h>
#include<cassert>

using namespace std;
#define ll long long
#define ld long double
//#define int long long
#define all(a) (a).begin(),(a).end()
#define EPS (1e-13)
#define fs first
#define sc second
#define xx first
#define yy second.first
#define zz second.second
#define H pair<int, int>
#define P pair<int, pair<int, int>>
#define Q(i,j,k) mkp(i,mkp(j,k))
#define rep(i,n) for(int (i) = 0 ; (i) < (n) ; (i)++)
#define mkp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define crdcomp(b) sort(all((b)));(b).erase(unique(all((b))),(b).end())
const int Mod = 1e9 + 7;
const int mod = 998244353;
const ll Inf = 3 * 1e18;
const int inf = 15 * 1e8;
ll read() {
	ll u, k = scanf("%lld", &u);
	return u;
}
ll gcd(ll i, ll j) {
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcd(j % i, i);
}
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}
ll bcount(ll x) {
	int sum = 0;
	for (int i = 0; i < 20; i++)
		if ((1ll << i) & x) sum++;
	return sum;
}
const int fn_ = 2000000;
ll fact_[fn_], comp_[fn_];
ll comb(ll x, ll y, ll mod = Mod) {
	if (!fact_[0]) {
		fact_[0] = 1; comp_[0] = 1;
		for (int i = 1; i < fn_; i++) {
			fact_[i] = fact_[i - 1] * i % mod;
			comp_[i] = mod_pow(fact_[i], mod - 2, mod);
		}
	}
	if (x < y) return 0;
	return fact_[x] * comp_[x - y] % mod * comp_[y] % mod;
}
//---------------------------------------------------
class RMQ {
#define H pair<int, int>
#define fs first
#define sc second
	int size, zero, m;
	H dat[500000];
public:
	void init(int a, int b) {
		size = a, zero = b;
		m = 1;
		while (m < size) m *= 2;
		for (int i = 0; i < 500000; i++) dat[i] = H{ zero,zero };
	}
	int query(int a, int b) {
		return query_(0, a, b, 0, m);
	}//0-indexed
	void update(int a, int b, int x) {
		update_(0, a, b, 0, m, x);
	}//0-indexed
private:
	void eval(int i, int l, int r) {
		if (r - l > 1) {
			if (zero > 0) {
				dat[i * 2 + 1].sc = min(dat[i * 2 + 1].sc, dat[i].sc);
				dat[i * 2 + 2].sc = min(dat[i * 2 + 2].sc, dat[i].sc);
			}
			else {
				dat[i * 2 + 1].sc = max(dat[i * 2 + 1].sc, dat[i].sc);
				dat[i * 2 + 2].sc = max(dat[i * 2 + 2].sc, dat[i].sc);
			}
		}
		if (zero <= 0) dat[i].fs = max(dat[i].fs, dat[i].sc);
		else dat[i].fs = min(dat[i].fs, dat[i].sc);
		dat[i].sc = zero;
	}
	int query_(int i, int a, int b, int l, int r) {
		eval(i, l, r);
		if (r <= a || b <= l) return zero;
		if (a <= l && r <= b) return dat[i].fs;
		if (zero > 0) return min(query_(i * 2 + 1, a, b, l, (l + r) / 2), query_(i * 2 + 2, a, b, (l + r) / 2, r));
		else return max(query_(i * 2 + 1, a, b, l, (l + r) / 2), query_(i * 2 + 2, a, b, (l + r) / 2, r));
	}
	void update_(int i, int a, int b, int l, int r, int x) {
		eval(i, l, r);
		if (r <= a || b <= l) return;
		if (a <= l && r <= b) {
			dat[i].sc = x;
			eval(i, l, r);
			return;
		}
		update_(i * 2 + 1, a, b, l, (l + r) / 2, x);
		update_(i * 2 + 2, a, b, (l + r) / 2, r, x);
		if (zero > 0) dat[i].fs = min(dat[i * 2 + 1].fs, dat[i * 2 + 2].fs);
		else dat[i].fs = max(dat[i * 2 + 1].fs, dat[i * 2 + 2].fs);
	}
};//size, 単位元
int n;
int a[300000], b[300000];
map<H, vector<H>>e;
RMQ odd, even;
H solve(int s, int t) {
	if (s == t) return H{ -1,0 };
	int k, r;
	if (s % 2 == 0) k = even.query(s, t);
	else k = odd.query(s, t);
	if (s % 2 == 0) r = odd.query(b[k] + 1, t);
	else r = even.query(b[k] + 1, t);
	e[H{ k,r }] = vector<H>();
	H g = solve(s, b[k]);
	if (g.fs > -1) e[H{ k,r }].push_back(g);
	g = solve(b[k] + 1, b[r]);
	if (g.fs > -1) e[H{ k,r }].push_back(g);
	g = solve(b[r] + 1, t);
	if (g.fs > -1) e[H{ k,r }].push_back(g);
	return H{ k,r };
}
signed main() {
	cin >> n;
	odd.init(n, inf);
	even.init(n, inf);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		b[a[i]] = i;
		if (i % 2 == 0) {
			even.update(i, i + 1, a[i]);
		}
		else {
			odd.update(i, i + 1, a[i]);
		}
	}
	priority_queue<H, vector<H>, greater<H>>p;
	p.push(solve(0, n));
	vector<int>ans;
	while (!p.empty()) {
		H t = p.top(); p.pop();
		ans.push_back(t.fs); ans.push_back(t.sc);
		for (auto g : e[t]) {
			p.push(g);
		}
	}
	for (int i = 0; i < n; i++) {
		cout << ans[i] << (i == n - 1 ? "\n" : " ");
	}
}

Measured memory_bytes: 39156