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 <cstring>
#include <cstdio>
#include <queue>
using namespace std;

const int S = 20;
const int N = 2e5 + 10;
const int inf = 0x3f3f3f3f;
int n, p[N], bin[30], log[N], st[N][S];
struct data {
	int l, r, x, y;
	data(int _l = 0, int _r = 0, int _x = 0, int _y = 0) {
		l = _l, r = _r, x = _x, y = _y;
	}
	inline bool operator < (const data &a) const {
		return p[x] == p[a.x] ? p[y] > p[a.y] : p[x] > p[a.x];
	}
}; priority_queue <data> q;

inline int query(int l, int r) {
	if (l & 1 ^ 1) l >>= 1, r >>= 1;
	else l = (l/2)+(n/2), r = (r-1)/2+(n/2);
	int d = log[r - l + 1];
	return p[st[r][d]]<p[st[l+bin[d]-1][d]] ? st[r][d] : st[l+bin[d]-1][d];
}

inline void add(int l, int r) {
	int x = query(l, r);
	int y = query(x + 1, r);
	q.push((data){l, r, x, y});
}

template <class T> inline void in(T &x) {
	x = 0; int f = 1; char ch = getchar();
	for (; ch<'0' || ch>'9';) {if (ch=='-') f=-1; ch = getchar();}
	for (; ch>='0' && ch<='9';) x = x*10 + ch-'0', ch = getchar();
	x *= f;
}

inline void init() {
	in(n), bin[0] = 1, memset(p, 0x3f, sizeof p);
	for (int i = 0; i < n; ++i) in(p[i]);
	for (int i = 1; i <= S; ++i) bin[i] = bin[i-1]<<1;
	for (int i = 0; i < n; ++i)
		st[(i/2) + (n/2)*(i%2)][0] = i, log[i] = i<2 ? 0 : log[i>>1]+1;
	for (int i = 1; i < S; ++i)
		for (int j = bin[i]-1, tmp = bin[i-1]; j < n; ++j)
			st[j][i] = p[st[j][i-1]] < p[st[j-tmp][i-1]] ? st[j][i-1] : st[j-tmp][i-1];
}

inline void work() {
	data u;
	for (add(0, n-1); !q.empty();) {
		u = q.top(), q.pop();
		printf("%d %d ", p[u.x], p[u.y]);
		if (u.l < u.x) add(u.l, u.x - 1);
		if (u.r > u.y) add(u.y + 1, u.r);
		if (u.x + 1 < u.y) add(u.x + 1, u.y - 1);
	}
}

int main() {init(), work(); return 0;}