#include <bits/stdc++.h>

using namespace std;

#define sqr(x) ((x) * (x))
#define pb push_back
#define mp make_pair
#define ins insert
#define X first
#define Y second
#define fin(name) freopen(name, "r", stdin)
#define fout(name) freopen(name, "w", stdout)
#define files(name) fin(name".in"); fout(name".out")
#define fi(st,n) for (int i = (st); i <= (int)(n); ++i)
#define fj(st,n) for (int j = (st); j <= (int)(n); ++j)
#define fk(st,n) for (int k = (st); k <= (int)(n); ++k)
#define fq(st,n) for (int q = (st); q <= (int)(n); ++q)
#define fw(st,n) for (int w = (st); w <= (int)(n); ++w)
#define ff(i, st, n) for (int (i) = (st); (i) <= (int)(n); ++(i))
#define ei(st,n) for (int i = (st); i >= (int)(n); --i)
#define ej(st,n) for (int j = (st); j >= (int)(n); --j)
#define ek(st,n) for (int k = (st); k >= (int)(n); --k)
#define ef(i, st, n) for (int (i) = (st); (i) >= (int)(n); --(i))
#define ri(st,n) for (int i = (st); i < (int)(n); ++i)
#define rj(st,n) for (int j = (st); j < (int)(n); ++j)
#define rk(st,n) for (int k = (st); k < (int)(n); ++k)
#define rq(st,n) for (int q = (st); q < (int)(n); ++q)
#define rf(i, st, n) for (int (i) = (st); (i) < (int)(n); ++(i))
#define clean(a) memset((a),0,sizeof (a))
#define sync ios_base::sync_with_stdio(0);cin.tie(0)
#define y1 dsklmlvmd

typedef long long ll;
typedef unsigned long long ull;
typedef double dbl;
typedef long double ldbl;

const int inf = (int)1e9;
const ll linf = (ll)1e18;
const dbl eps = (dbl) 1e-8;
const int mod = (int) 1e9 + 7;
const int maxn = (int) 2e5 + 5;
const int MX = (int) 1e5;
//const dbl M_PI = (dbl)2 * (dbl)acos(0);

//cout<<fixed<<setprecision(15);
//srand(time(0));

int n, a[maxn], pos[maxn];
vector <int> ans;
int t0[4 * maxn], t1[4 * maxn];

int build0(int v, int l, int r)
{
	if (l > r)
		return inf;
	if (l == r)
	{
		t0[v] = a[2 * l];
		return t0[v];
	}
	int m = (l + r) / 2;
	t0[v] = min(build0(2 * v, l, m), build0(2 * v + 1, m + 1, r));
	return t0[v];
}

int build1(int v, int l, int r)
{
	if (l > r)
		return inf;
	if (l == r)
	{
		t1[v] = a[2 * (l - 1) + 1];
		return t1[v];
	}
	int m = (l + r) / 2;
	t1[v] = min(build1(2 * v, l, m), build1(2 * v + 1, m + 1, r));
	return t1[v];
}

int dzen0(int v, int l, int r, int tl, int tr)
{
	if (tl > tr || l > r)
		return inf;
	if (l == tl && r == tr)
	{
		return t0[v];
	}
	int m = (l + r) / 2;
	return min(dzen0(2 * v, l, m, tl, min(tr, m)), dzen0(2 * v + 1, m + 1, r, max(tl, m + 1), tr));
}

int dzen1(int v, int l, int r, int tl, int tr)
{
	if (tl > tr || l > r)
		return inf;
	if (l == tl && r == tr)
	{
		return t1[v];
	}
	int m = (l + r) / 2;
	return min(dzen1(2 * v, l, m, tl, min(tr, m)), dzen1(2 * v + 1, m + 1, r, max(tl, m + 1), tr));
}

int main()
{
//    fin("t.in");
    sync;
    cin >> n;
    fi(1, n)
    {
    	cin >> a[i];
    	pos[a[i]] = i;
    }
    set <int> q;
    set <int> w;
    build0(1, 1, n / 2);
    build1(1, 1, n / 2);
    w.ins(dzen1(1, 1, n / 2, 1, n / 2));
    int u = 1;
    q.ins(0);
    q.ins(n + 1);
    ff(step, 1, n / 2)
    {
    	u = *w.begin();
    	w.erase(w.begin());
    	/*
    	while (1)
    	{
    		int fl = 1;
    		auto it = q.lower_bound(pos[u]);
    		if (*it <= pos[u] + 1)
    			fl = 0;
    		if ((*it - pos[u]) % 2 == 1)
    			fl = 0;
    		--it;
    		if ((pos[u] - *it) % 2 == 0)
    			fl = 0;
    		if (fl)
    			break;
    		++u;
    	}
    	*/
//    	cout << u << endl;
    	ans.pb(u);
    	int x;
    	int tl = (pos[u] + 1 - 1) / 2 + 1;
    	int tr = (*(q.lower_bound(pos[u])) - 2) / 2 + 1;
    	if (pos[u] & 1)
    	{
    		x = dzen0(1, 1, n / 2, tl, tr);
    	}
    	else
    	{
    		x = dzen1(1, 1, n / 2, tl, tr);
    	}
    	ans.pb(x);

    	int gl, gr;
    	auto it = q.lower_bound(pos[u]);
    	gr = *it;
    	--it;
    	gl = *it;

    	if (pos[u] - gl > 1)
    	{
//    		cout << "a" << endl;
    		int tl = (gl + 1 - 1) / 2 + 1;
    		int tr = (pos[u] - 3) / 2 + 1;
    		if (pos[u] & 1)
    			w.ins(dzen1(1, 1, n / 2, tl, tr));
    		else
    			w.ins(dzen0(1, 1, n / 2, tl, tr));
    	}
    	if (pos[x] - pos[u] > 1)
    	{
//    		cout << "b" << endl;
    		int tl = (pos[u] + 1 - 1) / 2 + 1;
    		int tr = (pos[x] - 3) / 2 + 1;
//    		cout << tl << " " << tr << endl;
    		if (pos[u] % 2 == 0)
    			w.ins(dzen1(1, 1, n / 2, tl, tr));
    		else
    			w.ins(dzen0(1, 1, n / 2, tl, tr));
    	}
    	if (gr - pos[x] > 1)
    	{
//    		cout << "c" << endl;
    		int tl = (pos[x] + 1 - 1) / 2 + 1;
    		int tr = (gr - 3) / 2 + 1;
    		if (pos[u] & 1)
    			w.ins(dzen1(1, 1, n / 2, tl, tr));
    		else
    			w.ins(dzen0(1, 1, n / 2, tl, tr));
    	}


    	q.ins(pos[u]);
    	q.ins(pos[x]);
    }
    ri(0, ans.size())
    {
    	cout << ans[i] << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 18420