#include <iostream>
#include <fstream>
#include <sstream>

#include <vector>
#include <set>
#include <bitset>
#include <map>
#include <deque>
#include <string>

#include <algorithm>
#include <numeric>

#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>

#define pb push_back
#define pbk pop_back
#define mp make_pair
#define fs first
#define sc second
#define all(x) (x).begin(), (x).end()
#define foreach(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i)
#define len(a) ((int) (a).size())

#ifdef CUTEBMAING
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) 42
#endif

using namespace std;

typedef long long int64;
typedef long double ld;
typedef unsigned long long lint;

const int inf = (1 << 30) - 1;
const int64 linf = (1ll << 62) - 1;
const int N = 1e6 + 100;

int n;

struct segtree {
	pair<int, int> rmq[N * 4 + 100];
	int wh[N];
	vector<int> v;
	int n;

	segtree(vector<int> v) : v(v) {
		n = len(v);
		make_rmq(1, 0, n - 1);
	}

	segtree(){}

	void make_rmq(int i, int l, int r) {
		if (l == r) {
			wh[l] = i;
			return void (rmq[i] = mp(v[l], l));
		}
		make_rmq(i * 2, l, (l + r) / 2);
		make_rmq(i * 2 + 1, (l + r) / 2 + 1, r);
		rmq[i] = min(rmq[i * 2], rmq[i * 2 + 1]);
	}

	pair<int, int> getValue(int i, int ll, int rr, int l, int r) {
		if (ll > r || rr < l) {
			return mp(inf, inf);
		}
		if (l <= ll && rr <= r) {
			return rmq[i];
		}
		return min(getValue(i * 2, ll, (ll + rr) / 2, l, r),
			getValue(i * 2 + 1, (ll + rr) / 2 + 1, rr, l, r));
	}

	void update(int i, pair<int, int> v) {
		i = wh[i];
		rmq[i] = v;
		for (i >>= 1; i; i >>= 1) {
			rmq[i] = min(rmq[i * 2], rmq[i * 2 + 1]);
		}
	}
};

vector<int> result;
segtree t0, t1;


pair<int, int> node_value[N];
vector<int> g[N];
int len = 0;

int solve(int l, int r);

int solveNext(int l, int r) {
	assert((r - l + 1) % 2 == 0);
	if (l > r) {
		return -1;
	}
	int first_index;
	int first_value;
	int second_index;
	int second_value;
	if (l % 2 == 0) {
		tie(first_value, first_index) = t0.getValue(1, 0, n - 1, l, r);
		auto index = first_index;
		auto value = first_value;
		t0.update(first_index, mp(inf, inf));
		tie(first_value, first_index) = t0.getValue(1, 0, n - 1, l, r);
		t0.update(index, mp(value, index));
		tie(second_value, second_index) = t1.getValue(1, 0, n - 1, first_index + 1, r);
	} else {
		tie(first_value, first_index) = t1.getValue(1, 0, n - 1, l, r);
		auto index = first_index;
		auto value = first_value;
		t0.update(first_index, mp(inf, inf));
		tie(first_value, first_index) = t1.getValue(1, 0, n - 1, l, r);
		t0.update(index, mp(value, index));
		tie(second_value, second_index) = t0.getValue(1, 0, n - 1, first_index + 1, r);
	}
	assert(second_index < n);
	t0.update(first_index, mp(inf, inf));
	t1.update(second_index, mp(inf, inf));
	int current_node = len++;
	node_value[current_node] = mp(first_value, second_value);
	g[current_node].pb(solve(l, first_index - 1));	
	g[current_node].pb(solve(first_index + 1, second_index - 1));
	g[current_node].pb(solve(second_index + 1, r));
	return current_node;
}

int solve(int l, int r) {
	assert((r - l + 1) % 2 == 0);
	if (l > r) {
		return -1;
	}
	int first_index;
	int first_value;
	int second_index;
	int second_value;
	if (l % 2 == 0) {
		tie(first_value, first_index) = t0.getValue(1, 0, n - 1, l, r);
		tie(second_value, second_index) = t1.getValue(1, 0, n - 1, first_index + 1, r);
	} else {
		tie(first_value, first_index) = t1.getValue(1, 0, n - 1, l, r);
		tie(second_value, second_index) = t0.getValue(1, 0, n - 1, first_index + 1, r);
	}
	if (second_index >= n) {
		return solveNext(l, r);
	}
	t0.update(first_index, mp(inf, inf));
	t1.update(second_index, mp(inf, inf));
	int current_node = len++;
	node_value[current_node] = mp(first_value, second_value);
	g[current_node].pb(solve(l, first_index - 1));	
	g[current_node].pb(solve(first_index + 1, second_index - 1));
	g[current_node].pb(solve(second_index + 1, r));
	return current_node;
}

int main() {
#ifdef XCODE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    cin >> n;
    vector<int> a, b;
    for (int i = 0; i < n; i++) {
    	int x; scanf("%d", &x);
    	if (i % 2 == 0) {
    		a.pb(x);
    		b.pb(inf);
    	} else {
    		a.pb(inf);
    		b.pb(x);
    	}
    }
    t0 = segtree(a);
    t1 = segtree(b);
    int root = solve(0, n - 1);

    vector<int> deg(len, 0);

    for (int i = 0; i < len; i++) {
    	for (int j : g[i]) {
    		if (j != -1) {
    			deg[j]++;
    		}
    	}
    }

    set<pair<pair<int, int>, int>> q;

    for (int i = 0; i < len; i++) {
    	if (deg[i] == 0) {
    		q.insert(make_pair(node_value[i], i));
    	}
    }

    while (!q.empty()) {
    	int v = q.begin()->sc;
    	q.erase(q.begin());
    	result.pb(node_value[v].fs);
    	result.pb(node_value[v].sc);
    	for (int to : g[v]) {
    		if (to == -1) {
    			continue;
    		}
    		--deg[to];
    		if (deg[to] == 0) {
    			q.insert(mp(node_value[to], to));
    		}
    	}
    }

    for (int i = 0; i < len(result); i++) {
    	printf("%d%c", result[i], " \n"[i + 1 == len(result)]);
    }
    return 0;
}


Measured memory_bytes: 198748