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 <utility>
#include <cstdio>
#include <queue>
#define mp std::make_pair
int arr[200005], bit[200005], n; 
std::pair<int, int> st[2][200005][25]; 
inline int query(int l, int r, int x)
{
	x ^= l & 1; 
	int len = bit[r - l + 1]; 
	return std::min(st[x][l][len], st[x][r - (1 << len) + 1][len]).second; 
}
struct data
{
	int l, r, x, y; 
	data(int _l, int _r)
	{
		l = _l; 
		r = _r; 
		x = query(l, r, 0); 
		y = query(x, r, 1); 
		fflush(stdout); 
	}
	inline bool operator <(const data &a) const
	{
		if (arr[x] == arr[a.x])
			return arr[y] > arr[a.y]; 
		return arr[x] > arr[a.x]; 
	}
}; 
std::priority_queue<data> que; 
inline void add(int l, int r)
{
	if (l < r)
		que.push(data(l, r)); 
}
int main()
{
	// freopen("ARC080-E.in", "r", stdin); 
	scanf("%d", &n); 
	for (int i = 0; i < n; i++)
	{
		scanf("%d", arr + i); 
		st[i & 1][i][0] = mp(arr[i], i);
		st[i & 1 ^ 1][i][0] = mp(1e9, i); 
	}
	for (int i = 2; i <= n; i++)
		bit[i] = bit[i >> 1] + 1; 
	for (int x = 0; x < 2; x++)
	{
		for (int j = 1; j < 20; j++)
		{
			for (int i = 0; i < n; i++)
			{
				st[x][i][j] = st[x][i][j - 1]; 
				if (i + (1 << j - 1) < n)
					st[x][i][j] = std::min(st[x][i][j], st[x][i + (1 << j - 1)][j - 1]); 
			}
		}
	}
	que.push(data(0, n - 1)); 
	while (!que.empty())
	{
		data u = que.top(); 
		que.pop(); 
		printf("%d %d ", arr[u.x], arr[u.y]);
		add(u.l, u.x - 1); 
		add(u.x + 1, u.y - 1); 
		add(u.y + 1, u.r); 
	}
	return 0; 
}
