#include <iostream>
#include <math.h>
#include <vector>
#include <stack>
#include <cstdio>
#include <string>
#include <bitset>
#include <list>
#include <set>
#include <algorithm>
#include <numeric>
#include <unordered_map>
#include <functional>
#include <queue>
#include <regex>
#include <cassert>
#include <map>
#include <type_traits>
#include <array>
// #include "bits/stdc++.h"

using namespace std;



namespace {
#define rep(i, N, M) for(int i=N, i##_len=(M); i<i##_len; ++i)
#define rep_skip(i, N, M, ...) for(int i=N, i##_len=(M); i<i##_len; i+=(skip))
#define rrep(i, N, M)  for(int i=(M)-1, i##_len=(N-1); i>i##_len; --i)
#define pb push_back


	typedef long long ll;
	typedef unsigned long long ull;
	typedef pair<ll, ll> pll;
	typedef tuple<ll, ll, ll> tll;
	typedef tuple<ll, ll, ll, ll> tll4;
	typedef tuple<ll, ll, ll, ll, ll> tll5;
	typedef tuple<ll, ll, ll, ll, ll, ll> tll6;

	typedef vector<ll> vll;
	typedef vector<vll> vvll;
	typedef vector<pll> vpll;
	typedef vector<bool> vb;
	typedef vector<vb> vvb;
	typedef vector<string> vs;
	template<typename T>
	using pq_greater = priority_queue<T,vector<T> ,greater<T>>;

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define vec(a) vector<a>
#define perm(c) sort(all(c));for(bool c##perm=1;c##perm;c##perm=next_permutation(all(c)))


	template<class T, class S>
	T atbit(T n, S i) {
		return (n >> i) % i;
	}

	template<class T>
	T getbit(T i) {
		return 1LL << i;
	}

	constexpr ll POW(ll n, ll m) {
		ll res = 1;
		rep(i, 0, m) {
			res *= n;
		}
		return res;
	}

	vll getDivisors(ll n) {
		vll res;
		ll i = 1;

		for (; i*i < n; i++) {
			if (n%i == 0) {
				res.push_back(i);
				res.push_back(n / i);
			}
		}
		if (i*i == n)res.push_back(i);
		sort(res.begin(), res.end());
		return res;
	}

	vll getDivisors(ll n, ll m) {
		if (n > m) swap(n, m);
		vll res;
		ll i = 1;

		for (; i*i < n; i++) {
			if (n%i == 0) {
				if (m%i == 0) res.push_back(i);
				if (m % (n / i) == 0) res.push_back(n / i);
			}
		}
		if (i*i == n) if (m%i == 0) res.push_back(i);
		sort(res.begin(), res.end());
		return res;
	}


	ll gcd(ll a, ll b) {
		if (a%b == 0) return b;
		else return gcd(b, a%b);
	}

	template<
		typename Inputs,
		typename Functor,
		typename T = typename Inputs::value_type>
		void sort_by(Inputs& inputs, Functor f) {
		std::sort(std::begin(inputs), std::end(inputs),
			[&f](const T& lhs, const T& rhs) { return f(lhs) < f(rhs); });
	}

	template<int I>
	vll proj(vpll v) {
		vll res(v.size());
		rep(i, 0, v.size()) {
			if (!I) res[i] = v[i].first;
			else res[i] = v[i].second;
		}
		return res;
	}


	template<int I, class T>
	vll proj(T v) {
		vll res(v.size());
		rep(i, 0, v.size()) {
			res[i] = get<I>(v[i]);
		}
		return res;
	}
	vector<pll >prime_factorize(ll n) {
		vector<pll> res;
		for (ll p = 2; p*p <= n; ++p) {
			if (n%p != 0)continue;
			ll num = 0;
			while (n%p == 0) { ++num; n /= p; }
			res.push_back({ p,num });
		}
		if (n != 1) res.push_back(make_pair(n, 1));
		return res;
	}

}

ll MOD = 1000000007;
ll INF = 1LL << 60;
ll n;

template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;

template <class Monoid>
struct segment_tree {
	typedef Monoid monoid_type;
	typedef typename Monoid::underlying_type underlying_type;
	ll n;
	vector<underlying_type> a;
	Monoid mon;
	segment_tree() = default;
	segment_tree(ll a_n, vector<underlying_type> initial_value = vector<underlying_type>(), 
		Monoid const & a_mon = Monoid())
		: size_(a_n), mon(a_mon) {
		n = 1; while (n < a_n) n *= 2;
		a.resize(2 * n - 1, mon.unit());
		//fill(a.begin() + (n - 1), a.begin() + (n - 1 + a_n), initial_value); // set initial values
		rep(i, 0, initial_value.size()) {
			a[i + (n - 1)] =  initial_value[i];
		}
		rrep(i,0, n-1) a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]); // propagate initial values
	}
	void point_set(int i, underlying_type z) { // 0-based
		a[i + n - 1] = z;
		for (i = (i + n) / 2; i > 0; i /= 2) { // 1-based
			a[i - 1] = mon.append(a[2 * i - 1], a[2 * i]);
		}
	}
	underlying_type range_concat(ll l, ll r) { // 0-based, [l, r)
		underlying_type lacc = mon.unit(), racc = mon.unit();
		for (l += n, r += n; l < r; l /= 2, r /= 2) { // 1-based loop, 2x faster than recursion
			if (l % 2 == 1) lacc = mon.append(lacc, a[(l++) - 1]);
			if (r % 2 == 1) racc = mon.append(a[(--r) - 1], racc);
		}
		return mon.append(lacc, racc);
	}
	ll size() { return size_; }
private :
	ll  size_;
};
template <typename T>
struct min_indexed_t {
	typedef pair<T, ll> underlying_type;
	underlying_type unit() const { return make_pair(numeric_limits<T>::max(), -1); }
	underlying_type append(underlying_type a, underlying_type b) const { return min(a, b); }
};
template <typename T>
struct min_t {
	typedef T underlying_type;
	underlying_type unit() const { return numeric_limits<T>::max(); }
	underlying_type append(underlying_type a, underlying_type b) const { return min(a, b); }
};


int main_() {
	vpll p = { {2, 1}, { 5,2 }, { 3,3 }, { 1,4 } };
	segment_tree<min_indexed_t<ll>> seg(4, p);
	cout << seg.range_concat(0,4).first;
	cout << seg.range_concat(0, 2).first;

	return 0;
}



int main() {
	// input
	ll n;
	cin >> n;
	vll p(n);
	rep(i, 0, n)cin >> p[i];
	vpll pe(n), po(n);
	rep(i, 0, n) {
		pe[i] = { i%2==1 ? 2LL<<60:p[i],i };
		po[i] = { i % 2 == 0 ? 2LL << 60 : p[i],i };
	}
	
	segment_tree<min_indexed_t<ll>>  even(n,pe), odd(n,po);
	pq_greater<tll6> pq;
	vpll res;

	auto push_pq=[&](ll l, ll r) {
		if (l == r)return;
		if (l % 2 == 0) {
			auto x = even.range_concat(l, r);
			auto y = odd.range_concat(x.second +1, r);
			pq.push(tll6{ x.first,y.first,x.second,y.second,l,r });
		}
		else
		{
			auto x = odd.range_concat(l, r);
			auto y = even.range_concat(x.second +1, r);
			pq.push(tll6{ x.first,y.first,x.second,y.second,l,r });
		}
	};
	push_pq(0, n);
	while (!pq.empty()) {
		ll x, y, x_ind, y_ind, l, r;
		tie(x, y, x_ind, y_ind, l, r) = pq.top();
		res.push_back({ x,y });
		pq.pop();
		push_pq(l, x_ind);
		push_pq(x_ind + 1, y_ind);
		push_pq(y_ind + 1, r);
	}

	rep(i, 0, n / 2-1) cout << res[i].first << " "<< res[i].second <<" ";
	cout << res[n / 2 - 1].first << " " << res[n / 2 - 1].second;
	return 0;
	
}



Measured memory_bytes: 33352