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
#include <cstdio>
#include <queue>
#include <algorithm>
int N, p[200001], ref[200001], RMQ[2][18][200001], LOG[200001];
struct tok
{
	int l, r, x, y;
};
struct com
{
	inline bool operator () (const tok &x, const tok &y)
	{
		return p[x.x] > p[y.x];
	}
};
inline int choose(int x, int y)
{
	return p[x] < p[y] ? x : y;
}
inline int Query(int f, int l, int r)
{
	int Log = LOG[r - l + 1];
	return choose(RMQ[f][Log][l], RMQ[f][Log][r - (1 << Log) + 1]);
}
std::priority_queue < tok, std::vector < tok >, com > Q;
tok make(int l, int r)
{
	int x = Query(l & 1, l, r - 1), y = Query(r & 1, x + 1, r);
	return { l, r, x, y };
}
int main()
{
	scanf("%d", &N);
	p[0] = 1000000000;
	for (int i = 1; i <= N; i++)
	{
		scanf("%d", p + i);
		ref[p[i]] = i;
		RMQ[i & 1][0][i] = i;
	}
	for (int i = 2; i <= N; i++)
		LOG[i] = LOG[i >> 1] + 1;
	for (int i = 1, k = 1; k + k <= N; i++, k <<= 1)
		for (int j = 1; j <= N - k - k + 1; j++)
		{
			RMQ[0][i][j] = choose(RMQ[0][i - 1][j], RMQ[0][i - 1][j + k]);
			RMQ[1][i][j] = choose(RMQ[1][i - 1][j], RMQ[1][i - 1][j + k]);
		}
	Q.push(make(1, N));
	for (int T = N >> 1; T--; )
	{
		tok D = Q.top();
		Q.pop();
		printf("%d %d ", p[D.x], p[D.y]);
		if (D.l < D.x)
			Q.push(make(D.l, D.x - 1));
		if (D.x < D.y - 1)
			Q.push(make(D.x + 1, D.y - 1));
		if (D.y < D.r)
			Q.push(make(D.y + 1, D.r));
	}
	puts("");
	return 0;
}
