#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>


template<typename T>
struct IndexedValue {
	T value; int index;
	bool operator<(const IndexedValue<T>& other) const { return value < other.value; }
};
template<typename T>
class MinSegmentTree {
	std::vector<std::vector<T>> vec;
	T min_inner(const int depth, const int from, const int until) const {
		auto length = 1 << depth;
		auto mid = (from + length - 1) / length * length;
		if (from == mid) {
			if (mid + length == until) return vec[depth][mid / length];
			else if (mid + length > until) return min_inner(depth - 1, from, until);
			else return std::min(vec[depth][mid / length], min_inner(depth, mid + length, until));
		}
		else if (mid >= until) {
			return min_inner(depth - 1, from, until);
		}
		else {
			if (mid + length == until) return std::min(min_inner(depth, from, mid), vec[depth][mid / length]);
			else if (mid + length > until) return std::min(min_inner(depth, from, mid), min_inner(depth, mid, until));
			else return std::min({ min_inner(depth, from, mid), vec[depth][mid / length], min_inner(depth, mid + length, until) });
		}
	}
public:
	MinSegmentTree(const std::vector<T>& defaults) : vec{ defaults } {
		while (vec.back().size() > 1) {
			std::vector<T> last_element; last_element.reserve(vec.back().size() / 2);
			for (auto i = 0; i < vec.back().size() / 2; ++i) {
				last_element.push_back(std::min(vec.back()[i * 2], vec.back()[i * 2 + 1]));
			}
			vec.push_back(std::move(last_element));
		}
	}
	MinSegmentTree(const int _size, const T& default_value): MinSegmentTree(std::vector<T>(_size, default_value)){};
	T min_of(const int from, const int until) const { return min_inner(vec.size() - 1, from, until); }
	void update(int position, const T& value) {
		vec[0][position] = value; position /= 2;
		for (auto i = 1; i < vec.size() && position < vec[i].size(); ++i) {
			vec[i][position] = std::min(vec[i - 1][position * 2], vec[i - 1][position * 2 + 1]);
			position /= 2;
		}
	}
};
struct Range {
	int from, until;
};
int main() {
	int n; std::cin >> n;
	std::vector<int> numbers(n); for (auto& a : numbers) std::cin >> a;
	MinSegmentTree<IndexedValue<int>> odd(n, IndexedValue<int>{ INT_MAX, -1 }), even(n, IndexedValue<int>{INT_MAX, -1});
	for (auto i = 0; i < n; ++i) {
		if (i % 2 == 0) {
			even.update(i, IndexedValue<int>{numbers[i], i});
		}
		else {
			odd.update(i, IndexedValue<int>{numbers[i], i});
		}
	}
	auto comparator = [](const std::pair<Range, int>& a, const std::pair<Range, int>& b) {return a.second > b.second; };
	std::priority_queue<std::pair<Range, int>, std::vector<std::pair<Range, int>>, decltype(comparator)> queue(comparator);
	queue.emplace(Range{ 0, n }, even.min_of(0, n).value);
	std::vector<int> result;
	while (!queue.empty()) {
		auto top = queue.top(); queue.pop();
		if (top.first.from % 2 == 0) {
			auto min = even.min_of(top.first.from, top.first.until);
			result.push_back(min.value);
			auto second_min = odd.min_of(min.index + 1, top.first.until);
			result.push_back(second_min.value);
			if (top.first.from != min.index) queue.emplace(Range{ top.first.from, min.index }, even.min_of(top.first.from, min.index).value);
			if (min.index + 1 < second_min.index) queue.emplace(Range{ min.index + 1, second_min.index }, odd.min_of(min.index + 1, second_min.index).value);
			if (second_min.index + 1 < top.first.until) queue.emplace(Range{ second_min.index + 1, top.first.until }, even.min_of(second_min.index + 1, top.first.until).value);
		}
		else {
			auto min = odd.min_of(top.first.from, top.first.until);
			result.push_back(min.value);
			auto second_min = even.min_of(min.index + 1, top.first.until);
			result.push_back(second_min.value);
			if (top.first.from != min.index) queue.emplace(Range{ top.first.from, min.index }, odd.min_of(top.first.from, min.index).value);
			if (min.index + 1 < second_min.index) queue.emplace(Range{ min.index + 1, second_min.index }, even.min_of(min.index + 1, second_min.index).value);
			if (second_min.index + 1 < top.first.until) queue.emplace(Range{ second_min.index + 1, top.first.until }, odd.min_of(second_min.index + 1, top.first.until).value);
		}
	}
	for (auto i = 0; i < n; ++i) {
		if (i != 0) std::cout << ' ';
		std::cout << result[i];
	}
	std::cout << std::endl;
}

Measured memory_bytes: 11360