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 <bits/stdc++.h>
using namespace std;
#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define mp(a, b) make_pair(a, b)
typedef pair<int, int> pii;
const int maxn = 2e5 + 10;
const int INF = 1e9;
int n, p[maxn];
pii Min[2][maxn << 2];
struct Seg
{
	int l, r;
	pii pos;
};
struct cmp
{
	bool operator () (const Seg & i, const Seg & j)
	{
		return p[i.pos.first] > p[j.pos.first];
	}
};
priority_queue<Seg, vector<Seg>, cmp> Q;
void pushup(int rt)
{
	Min[0][rt] = min(Min[0][ls], Min[0][rs]);
	Min[1][rt] = min(Min[1][ls], Min[1][rs]);
}
void build(int rt, int l, int r)
{
	if(l == r)
	{
		int id = l & 1;
		Min[id][rt] = mp(p[l], l);
		Min[id ^ 1][rt] = mp(INF, l);
		return;
	}
	int mid = l + r >> 1;
	build(ls, l, mid); build(rs, mid + 1, r);
	pushup(rt);
}
pii query(int rt, int l, int r, int a, int b)
{
	if(a <= l && r <= b) return Min[a & 1][rt];
	int mid = l + r >> 1;
	if(b <= mid) return query(ls, l, mid, a, b);
	if(a > mid) return query(rs, mid + 1, r, a, b);
	return min(query(ls, l, mid, a, b), query(rs, mid + 1, r, a, b));
}
pii getPos(int l, int r)
{
	pii p1 = query(1, 1, n, l, r);
	pii p2 = query(1, 1, n, p1.second + 1, r);
	return mp(p1.second, p2.second);
}
void ins(int l, int r)
{
	if(l > r) return;
	Q.push(Seg{l, r, getPos(l, r)});
}
void solve()
{
	vector<int> ans;
	ins(1, n);
	while(!Q.empty())
	{
		Seg x = Q.top(); Q.pop();
		ans.push_back(p[x.pos.first]);
		ans.push_back(p[x.pos.second]);
		ins(x.l, x.pos.first - 1);
		ins(x.pos.first + 1, x.pos.second - 1);
		ins(x.pos.second + 1, x.r);
	}
	for(auto v : ans) printf("%d ", v);
}
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) scanf("%d", &p[i]);
	build(1, 1, n);
	solve();
	return 0;
}