#include <iostream>
#include <limits>
#include <vector>
#include <map>
#include <queue>
#include <functional>
#include <algorithm>
using namespace std;

template<typename Type> class RangeMin {
private:
	int size_;
	std::vector<Type> dat;
public:
	RangeMin() : size_(0), dat(std::vector<Type>()) {};
	RangeMin(int size__) {
		for (size_ = 1; size_ < size__; ) size_ <<= 1;
		dat.resize(size_ << 1, std::numeric_limits<Type>::max());
	}
	template<class T>
	RangeMin(T begin_, T end_) {
		int n = end_ - begin_;
		for (size_ = 1; size_ < n; size_ <<= 1); dat.resize(size_ << 1, std::numeric_limits<Type>::max());
		for (int i = 0; i < n; i++) dat[i + size_] = *(begin_ + i);
		for (int i = size_ - 1; i > 0; i--) dat[i] = std::min(dat[i << 1], dat[(i << 1) + 1]);
	}
	inline unsigned size() { return size_; }
	inline void update(int i, Type x) {
		i += size_; dat[i] = x;
		while (i > 1) {
			i >>= 1;
			dat[i] = std::min(dat[i << 1], dat[i << 1 | 1]);
		}
	}
	inline Type query(int l, int r) {
		Type ret = std::numeric_limits<Type>::max();
		l += size_; r += size_;
		while (l != r) {
			if (l & 1) ret = std::min(ret, dat[l++]); l >>= 1;
			if (r & 1) ret = std::min(ret, dat[--r]); r >>= 1;
		}
		return ret;
	}
};

int N, A[1 << 18];
RangeMin<long long> X1, X2; map<pair<int, int>, vector<pair<int, int>>>Map;
map<pair<int, int>, pair<int, int>>I, II;

pair<int, int> solve(int L, int R, bool istrans) {
	if (L > R) return make_pair(0, 0);

	if (istrans == false) {
		long long V1 = X1.query(L, R + 1); pair<long long, long long>A1 = make_pair(V1 / 1000000LL, V1 % 1000000LL);
		long long V2 = X2.query(A1.second + 1, R + 1); pair<long long, long long>A2 = make_pair(V2 / 1000000LL, V2 % 1000000LL);

		pair<int, int>L1 = solve(L, A1.second - 1, istrans);
		pair<int, int>L2 = solve(A1.second + 1, A2.second - 1, istrans ^ true);
		pair<int, int>L3 = solve(A2.second + 1, R, istrans);
		if (L1 != make_pair(0, 0)) Map[make_pair(L, R)].push_back(make_pair(L, A1.second - 1));
		if (L2 != make_pair(0, 0)) Map[make_pair(L, R)].push_back(make_pair(A1.second + 1, A2.second - 1));
		if (L3 != make_pair(0, 0)) Map[make_pair(L, R)].push_back(make_pair(A2.second + 1, R));
		I[make_pair(L, R)] = make_pair(A[A1.second], A[A2.second]);
		II[make_pair(A[A1.second], A[A2.second])] = make_pair(L, R);
		return make_pair(L, R);
	}
	if (istrans == true) {
		long long V1 = X2.query(L, R + 1); pair<long long, long long>A1 = make_pair(V1 / 1000000LL, V1 % 1000000LL);
		long long V2 = X1.query(A1.second + 1, R + 1); pair<long long, long long>A2 = make_pair(V2 / 1000000LL, V2 % 1000000LL);

		pair<int, int>L1 = solve(L, A1.second - 1, istrans);
		pair<int, int>L2 = solve(A1.second + 1, A2.second - 1, istrans ^ true);
		pair<int, int>L3 = solve(A2.second + 1, R, istrans);
		if (L1 != make_pair(0, 0)) Map[make_pair(L, R)].push_back(make_pair(L, A1.second - 1));
		if (L2 != make_pair(0, 0)) Map[make_pair(L, R)].push_back(make_pair(A1.second + 1, A2.second - 1));
		if (L3 != make_pair(0, 0)) Map[make_pair(L, R)].push_back(make_pair(A2.second + 1, R));
		I[make_pair(L, R)] = make_pair(A[A1.second], A[A2.second]);
		II[make_pair(A[A1.second], A[A2.second])] = make_pair(L, R);
		return make_pair(L, R);
	}
}

int main() {
	cin >> N; X1 = RangeMin<long long>(N + 2); X2 = RangeMin<long long>(N + 2);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		if (i % 2 == 0) X1.update(i, A[i] * 1000000LL + i);
		if (i % 2 == 1) X2.update(i, A[i] * 1000000LL + i);
	}
	pair<int, int>G = solve(0, N - 1, false);

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>Q;
	Q.push(I[G]); vector<int>Z;

	while (!Q.empty()) {
		pair<int, int> pos1 = Q.top(); Z.push_back(pos1.first); Z.push_back(pos1.second); Q.pop();
		pos1 = II[pos1];
		vector<pair<int, int>>Z = Map[pos1];
		for (int i = 0; i < Z.size(); i++) Q.push(I[Z[i]]);
	}
	for (int i = 0; i < Z.size(); i++) {
		if (i) cout << " "; cout << Z[i];
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 45812