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<cmath>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 3e5 + 7;
const int logn = 19;
int n;
int bin[logn], lg[maxn];
int pos[maxn];
struct seg
{
	int l, r, x, y;
};
inline bool operator < (const seg &u, const seg &v)
{
	if(u.x != v.x) return u.x > v.x;
	return u.y > v.y;
}
priority_queue <seg> q;
inline int Get()
{
	char c;
	while(!isdigit(c = getchar()));
	int x = c - '0';
	while(isdigit(c = getchar()))
		x = x * 10 + c - '0';
	return x;
}
struct minimum
{
	int x, y, ans[maxn][logn];
	inline void Init()
	{
		memset(ans, 127 / 2, sizeof(ans));
	}
	inline void Rmq()
	{
		for(int k = 1; k < logn; ++k)
			for(int i = 1; i <= n; ++i)
			{
				if(i + bin[k] - 1 > n) break;
				ans[i][k] = min(ans[i][k - 1], ans[i + bin[k - 1]][k - 1]);
			}
	}
	inline int Min(int l, int r)
	{
		int len = lg[r - l + 1];
		return min(ans[l][len], ans[r - bin[len] + 1][len]);
	}
};
minimum a, b;
inline void Push(int l, int r)
{
	if(r - l < 1) return;
	int x, y;
	if(l & 1)
	{
		x = a.Min(l, r);
		y = b.Min(pos[x] + 1, r);
	}
	else
	{
		x = b.Min(l, r);
		y = a.Min(pos[x] + 1, r);
	}
	q.push((seg) {l, r, x, y});
}
int main()
{
	n = Get();
	a.Init(), b.Init();
	for(int i = 1; i <= n; ++i)
	{
		int x = Get();
		if(i & 1) a.ans[i][0] = x;
		else b.ans[i][0] = x;
		pos[x] = i;
	}
	lg[1] = 0;
	for(int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
	bin[0] = 1;
	for(int i = 1; i < logn; ++i) bin[i] = bin[i - 1] << 1;
	a.Rmq(), b.Rmq();
	Push(1, n);
	seg w;
	while(!q.empty())
	{
		w = q.top(), q.pop();
		printf("%d %d ", w.x, w.y);
		Push(w.l, pos[w.x] - 1);
		Push(pos[w.x] + 1, pos[w.y] - 1);
		Push(pos[w.y] + 1, w.r);
	}
}