Problem: Let N be a positive even number.

We have a permutation of (1, 2, ..., N), p = (p_1, p_2, ..., p_N). Snuke is constructing another permutation of (1, 2, ..., N), q, following the procedure below.

First, let q be an empty sequence. Then, perform the following operation until p becomes empty:

* Select two adjacent elements in p, and call them x and y in order. Remove x and y from p (reducing the length of p by 2), and insert x and y, preserving the original order, at the beginning of q.



When p becomes empty, q will be a permutation of (1, 2, ..., N).

Find the lexicographically smallest permutation that can be obtained as q.

Constraints

* N is an even number.
* 2 ≤ N ≤ 2 × 10^5
* p is a permutation of (1, 2, ..., N).

Input

Input is given from Standard Input in the following format:


N
p_1 p_2 ... p_N


Output

Print the lexicographically smallest permutation, with spaces in between.

Examples

Input

4
3 2 4 1


Output

3 1 2 4


Input

2
1 2


Output

1 2


Input

8
4 6 3 2 8 5 7 1


Output

3 1 2 7 4 6 8 5

Solution (in CPP):

Solution:
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;

inline int getint()
{
	static char c;
	while ((c = getchar()) < '0' || c > '9');

	int res = c - '0';
	while ((c = getchar()) >= '0' && c <= '9')
		res = res * 10 + c - '0';
	return res;
}

const int MaxN = 200000;
const int MaxLogN = 17;
const int INF = 0x3f3f3f3f;

int n;
int a[MaxN + 1];

int val[2][MaxLogN + 1][MaxN + 1];

int log_t[MaxN + 1];

inline int mymin(int i, int j)
{
	return a[i] < a[j] ? i : j;
}

inline void build_table(int val[MaxLogN + 1][MaxN + 1])
{
	for (int k = 0; k < log_t[n]; ++k)
	{
		int up = n - (1 << k + 1) + 1;
		for (int i = 1; i <= up; ++i)
			val[k + 1][i] = mymin(val[k][i], val[k][i + (1 << k)]);
	}
}

inline int query(int d, int l, int r)
{
	int k = log_t[r - l + 1];
	int vl = val[d][k][l];
	int vr = val[d][k][r - (1 << k) + 1];
	return mymin(vl, vr);
}

struct object
{
	int l, r, p, q;
	object() {}
	object(const int &_l, const int &_r)
		: l(_l), r(_r)
	{
		p = query(l & 1, l, r);
		q = query(r & 1, p, r);
	}

	friend inline bool operator<(const object &lhs, const object &rhs)
	{
		return a[lhs.p] > a[rhs.p];
	}
};

priority_queue<object> q;

int main()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		a[i] = getint();

		int u = i & 1, v = !u;
		val[u][0][i] = i;
		val[v][0][i] = 0;
	}

	a[0] = INF;

	log_t[1] = 0;
	for (int i = 2; i <= n; ++i)
		log_t[i] = log_t[i >> 1] + 1;

	build_table(val[0]);
	build_table(val[1]);

	q.emplace(1, n);
	while (!q.empty())
	{
		object cur = q.top();
		q.pop();

		printf("%d %d ", a[cur.p], a[cur.q]);

		if (cur.l < cur.p)
			q.emplace(cur.l, cur.p - 1);
		if (cur.p < cur.q - 1)
			q.emplace(cur.p + 1, cur.q - 1);
		if (cur.q < cur.r)
			q.emplace(cur.q + 1, cur.r);
	}

	return 0;
}