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<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 200005;
struct sb{
	int l, r, x, y;
	inline bool operator < (const sb &b) const
	{
		return x > b.x;
	}
};
priority_queue <sb> q;
int n, m, i, j, k, x, y, a[MAXN], f[20][MAXN], Lg[MAXN], b[MAXN], g[20][MAXN];
inline int getji(int l, int r)
{
	int k = Lg[r - l + 1];
	return min(f[k][l], f[k][r - (1 << k) + 1]);
}
inline int getou(int l, int r)
{
	int k = Lg[r - l + 1];
	return min(g[k][l], g[k][r - (1 << k) + 1]);
}
inline void solve(int l, int r)
{
	if (r < l) return;
	if (l & 1)
	{
		x = getji(l, r);
		y = getou(b[x] + 1, r);
		q.push((sb){l, r, x, y});
	}
	else
	{
		x = getou(l, r);
		y = getji(b[x] + 1, r);
	//	cout << x << " " << y << endl;
		q.push((sb){l, r, x, y});
	}
}
int main()
{
	cin >> n;
	memset(f, 127 / 3, sizeof(f));
	memset(g, 127 / 3, sizeof(g));
	for(i = 1; i <= n; i ++)
	{
		scanf("%d", &a[i]), b[a[i]] = i;
		if (i & 1) f[0][i] = a[i];
		else g[0][i] = a[i];
	}
	Lg[0] = -1;
	for(i = 1; i <= n; i ++)
		Lg[i] = Lg[i >> 1] + 1;
	for(j = 1; j <= Lg[n]; j ++)
		for(i = 1; i <= n - (1 << j) + 1; i ++)
		{
			f[j][i] = min(f[j - 1][i], f[j - 1][i + (1 << j - 1)]);
			g[j][i] = min(g[j - 1][i], g[j - 1][i + (1 << j - 1)]);
		}
	x = getji(1, n);
	y = getou(b[x] + 1, n);
	q.push((sb){1, n, x, y});
	for(i = 1; i * 2 <= n; i ++)
	{
		sb t = q.top();
		q.pop();
		printf("%d %d ", t.x, t.y);
		solve(t.l, b[t.x] - 1);
		solve(b[t.x] + 1, b[t.y] - 1);
		solve(b[t.y] + 1, t.r);
	}
}