#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
using namespace std;
using LL = long long;


//Base class for Segment Trees
template <class T>
class segtree_base
{
protected:
	size_t width;
	vector<T> vec;
	T def;
	virtual T query_raw(int l_, int r_, int a_, int b_, int k_) = 0;
public:
	segtree_base(size_t size_, T def_ = T()) : def(def_)
	{
		width = 1;
		while (width < size_)width *= 2;
		vec.resize(width * 2 - 1, def);
	}
	//Ask a query in ranges [left,right)
	T query(int left, int right)
	{
		return query_raw(left, right, 0, width, 0);
	}
	//Get the number of child nodes
	size_t treeWidth()
	{
		return width;
	}
	virtual ~segtree_base() {}
};

#include <algorithm>
//Range Minimum Tree
template <class T, class Comp>
class rmq_tree : public segtree_base<T>
{
public:
	rmq_tree(size_t size_) : segtree_base<T>(size_, make_pair(INT_MAX,INT_MAX))
	{}

	//Do [] <= base
	void init(const vector<T>&base)
	{
		for (int i = 0; i < min(this->width, base.size()); i++) this->vec[i + this->width - 1] = base[i];
		for (int i = this->width - 2; i >= 0; i--) this->vec[i] = std::min(this->vec[i * 2 + 1], this->vec[i * 2 + 2], Comp());
	}

	//Make [index] <= val;
	void update(int index, T val)
	{
		auto &vec = this->vec;
		index += (this->width - 1);
		vec[index] = val;
		while (index > 0)
		{
			index = (index - 1) / 2;
			vec[index] = std::min(vec[index * 2 + 1], vec[index * 2 + 2], Comp());
		}
	}
private:
	T query_raw(int l_, int r_, int a_, int b_, int k_)override
	{
		const auto &vec = this->vec;
		if (l_ <= a_ && b_ <= r_)
		{
			return vec[k_];
		}
		if (b_ <= l_ || r_ <= a_)
		{
			return this->def;
		}
		int m = (a_ + b_) / 2;
		return std::min(
			query_raw(l_, r_, a_, m, k_ + k_ + 1),
			query_raw(l_, r_, m, b_, k_ + k_ + 2), Comp());
	}
};

class Compare
{
public:
	bool operator()(pair<pair<int, int>,int> n1, pair<pair<int, int>,int> n2)
	{
		if (n1.first.first == n2.first.first)
		{
			if (n1.first.second == n2.first.second)
			{
				return n1.second > n2.second;
			}
			return n1.first.second > n2.first.second;
		}
		return n1.first.first > n2.first.first;
	}
};

//Functors for Segment Trees
template <class T>
struct my_less : std::less<T>
{
	static constexpr T defval = std::numeric_limits<T>::max();
};

template<>
struct my_less<pair<int,int>> : std::less<pair<int,int>>
{
	static constexpr pair<int, int> defval = pair<int,int>();
};

using segment = rmq_tree < pair<int, int>, my_less<pair<int, int>>>;

pair<int, int>vert[214514];
vector<int>dag[214514];
vector<segment>sg;
int N;

int ceil(int a, int b)
{
	assert(a >= 0);
	if (a == 0)return 0;
	return (a - 1) / b + 1;
}

int NEXT_V = 0;
int next_v()
{
	NEXT_V++;
	return NEXT_V - 1;
}

int main(void)
{
	cin >> N;
	sg.push_back(segment(N / 2));
	sg.push_back(segment(N / 2));
	for (int i = 0; i < N; ++i)
	{
		int p; cin >> p;
		sg[i % 2].update(i / 2, make_pair(p, i));
	}
	function<void(int, int, int, bool)>f = [&](int L, int R, int now, bool turn)
	{
		assert((R - L) % 2 == 0);
		assert(R - L);
		pair<int, int> one, two;
		if (turn)
		{
			//反転
			one = sg[1].query(L / 2, R / 2);
			two = sg[0].query(ceil(one.second, 2), ceil(R, 2));
		}
		else
		{
			//反転していない
			one = sg[0].query(ceil(L, 2), ceil(R, 2));
			two = sg[1].query(one.second / 2, R / 2);
		}
		vert[now] = make_pair(one.first, two.first);
		if (L < one.second)
		{
			int next = next_v();
			dag[now].push_back(next);
			f(L, one.second, next, turn ^ false);
		}
		if (one.second + 1 < two.second)
		{
			int next = next_v();
			dag[now].push_back(next);
			f(one.second + 1, two.second, next, turn ^ true);
		}
		if (two.second + 1 < R)
		{
			int next = next_v();
			dag[now].push_back(next);
			f(two.second + 1, R, next, turn ^ false);
		}
	};
	f(0, N, next_v(), false);
	priority_queue<pair<pair<int, int>, int>,vector<pair<pair<int, int>, int>>,Compare>que;
	//first:値　second:index
	que.push(make_pair(vert[0], 0));
	vector<int>ans;
	while (!que.empty())
	{
		auto p = que.top(); que.pop();
		ans.push_back(p.first.first);
		ans.push_back(p.first.second);
		for (int next : dag[p.second])
		{
			que.push(make_pair(vert[next], next));
		}
	}
	for (int i = 0; i < N; ++i)
	{
		cout << ans[i] << " \n"[i == N - 1];
	}
	return 0;
}


Measured memory_bytes: 40056