/*
* C++11 code template for contests.
* @author: Andrey Kalendarov
* @e-mail: andreykalendarov@gmail.com
*/

#pragma GCC optimize ("O3")
//#define ANDREIKKAA_TOPCODER
//#define ANDREIKKAA_ALLOCATOR
#define ANDREIKKAA_CLASS Solution
#define ANDREIKKAA_METHOD solve
#define ANDREIKKAA_PARAMETERS void
#define ANDREIKKAA_CALL
#define ANDREIKKAA_RETURN_TYPE void

#define first x
#define second y
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef double ld;

#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
const ld PI = acos(-1);

const int _ML = 250;
const char _inpf[] =
#if defined(ANDREIKKAA)
"input.txt"
#else
""
#endif
;
const char _outf[] =
#if defined(ANDREIKKAA)
""
#else
""
#endif
;

#if defined(ANDREIKKAA_ALLOCATOR)
char _mem[_ML * 1024LL * 1024LL];
size_t _ptr = 0;
inline void* operator new(size_t _x) { _ptr += _x; return _mem + _ptr - _x; }
inline void operator delete(void*) { }
#endif

template<typename T, typename U> inline ostream &operator << (ostream &_out, const pair<T, U> &_p) { _out << _p.first << ' ' << _p.second; return _out; }
template<typename T, typename U> inline istream &operator >> (istream &_in, pair<T, U> &_p) { _in >> _p.first >> _p.second; return _in; }
template<typename T> inline ostream &operator << (ostream &_out, const vector<T> &_v) { if (_v.empty()) return _out; _out << _v.front(); for (auto _it = ++_v.begin(); _it != _v.end(); ++_it) _out << ' ' << *_it; return _out; }
template<typename T> inline istream &operator >> (istream &_in, vector<T> &_v) { for (auto &_i : _v) _in >> _i; return _in; }
template<typename T> inline ostream &operator << (ostream &_out, const set<T> &_s) { if (_s.empty()) return _out; _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) _out << ' ' << *_it; return _out; }
template<typename T> inline ostream &operator << (ostream &_out, const multiset<T> &_s) { if (_s.empty()) return _out; _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) _out << ' ' << *_it; return _out; }
template<typename T> inline ostream &operator << (ostream &_out, const unordered_set<T> &_s) { if (_s.empty()) return _out; _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) _out << ' ' << *_it; return _out; }
template<typename T> inline ostream &operator << (ostream &_out, const unordered_multiset<T> &_s) { if (_s.empty()) return _out; _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) _out << ' ' << *_it; return _out; }
template<typename T, typename U> inline ostream &operator << (ostream &_out, const map<T, U> &_m) { if (_m.empty()) return _out; _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) _out << ", (" << _it->first << ": " << _it->second << ')'; return _out; }
template<typename T, typename U> inline ostream &operator << (ostream &_out, const unordered_map<T, U> &_m) { if (_m.empty()) return _out; _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) _out << ", (" << _it->first << ": " << _it->second << ')'; return _out; }

/* ________ CODE ________ */

const int N = 200 * 1000;
const int INF = 228228228;

struct
{
	pair<int, int> mn0 = {INF, -1};
	pair<int, int> mn1 = {INF, -1};
} t[4 * N];

pair<int, int> get_t(int v, int l, int r, int L, int R, bool p)
{
	if(R <= l || r <= L)
	{
		return {INF, -1};
	}

	if(L <= l && r <= R)
	{
		if(p)
		{
			return t[v].mn1;
		}
		else
		{
			return t[v].mn0;
		}
	}

	return min(
	get_t(v << 1, l, (l + r) >> 1, L, R, p),
	get_t(v << 1 | 1, (l + r) >> 1, r, L, R, p)
	);
}

void build_t(int v, int l, int r, vector<int> &a)
{
	if(r - l == 1)
	{
		if(l & 1)
		{
			t[v].mn1 = {a[l], l};
		}
		else
		{
			t[v].mn0 = {a[l], l};
		}
	}
	else
	{
		build_t(v << 1, l, (l + r) >> 1, a);
		build_t(v << 1 | 1, (l + r) >> 1, r, a);
		t[v].mn0 = min(t[v << 1].mn0, t[v << 1 | 1].mn0);
		t[v].mn1 = min(t[v << 1].mn1, t[v << 1 | 1].mn1);
	}
}

int n;
vector<int> v;

struct ans
{
	pair<int, int> p;
	vector<ans*> v;
};

bool operator<(const ans &a, const ans &b)
{
	return a.p < b.p;
}

ans* solve(int l, int r, bool p)
{
	assert(((r - l) & 1) == 0); 
	if(r - l == 0)
	{
		return nullptr;
	}

	int p1 = get_t(1, 0, n, l, r, p).y;
	int p2 = get_t(1, 0, n, p1 + 1, r, !p).y;
	
	ans *a = new ans;
	a->p = {v[p1], v[p2]};
	
	auto a1 = solve(l, p1, p);
	auto a2 = solve(p1 + 1, p2, !p);
	auto a3 = solve(p2 + 1, r, p);
	
	if(a1 != nullptr)
		a->v.push_back(a1);
	if(a2 != nullptr)
		a->v.push_back(a2);
	if(a3 != nullptr)
		a->v.push_back(a3);
	
	return a;
}

inline ANDREIKKAA_RETURN_TYPE mainFunction(ANDREIKKAA_PARAMETERS)
{
	cin >> n;
	v.resize(n);
	cin >> v;

	build_t(1, 0, n, v);
	
	auto r = solve(0, n, 0);
	
	set<ans> s;
	s.insert(*r);

	while(!s.empty())
	{
		auto p = *s.begin();
		s.erase(s.begin());
		
		cout << p.p << " ";

		for(auto i : p.v)
		{
			s.insert(*i);
		}
	}
	cout << endl;
}


/* ________ CODE ________ */

#if defined(ANDREIKKAA) || !defined(ANDREIKKAA_TOPCODER)
int main()
{
#if defined(ANDREIKKAA)
	time_t _start = clock();
#endif
	if (_inpf[0] != '\0')
		assert(freopen(_inpf, "r", stdin) != nullptr);
	if (_outf[0] != '\0')
		assert(freopen(_outf, "w", stdout) != nullptr);
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << setprecision(20);
	//cout << fixed;	
	mainFunction(ANDREIKKAA_CALL);
#if defined(ANDREIKKAA)
	cerr << "Time: " << (clock() - _start) / (ld)CLOCKS_PER_SEC << endl;
	//while (true);
#endif
}
#else
class ANDREIKKAA_CLASS { public: ANDREIKKAA_RETURN_TYPE ANDREIKKAA_METHOD(ANDREIKKAA_PARAMETERS) { return mainFunction(ANDREIKKAA_CALL); } };
#endif

Measured memory_bytes: 32384