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:
// Young Maids
// * frank_c1
// * 2017 / 09 / 27 

#include <bits/stdc++.h>
using namespace std;

const int maxn = (int)(2e5) + 5;
int a[maxn], ps[maxn], T[maxn << 2][2], M;

inline int Q(int s, int t, int c) {
	int ret = (int)(1e9);
	for (s += M - 1, t += M + 1; s ^ t ^ 1; s >>= 1, t >>= 1) {
		if (~s & 1) ret = min(ret, T[s ^ 1][c]);
		if ( t & 1) ret = min(ret, T[t ^ 1][c]);
	} return ret;
}

struct node {
	int l, r, c, s, t;

	node(int _l, int _r, int _c) {
		l = _l; r = _r; c = _c;
		s = ps[Q(l, r, c)]; t = ps[Q(s, r, c ^ 1)];
	}
};

bool operator < (node x, node y) {
	return a[x.s] > a[y.s];
}

priority_queue<node> q;

int main() {
	int n;
	scanf("%d", &n);
	for (M = 1; M <= n; M <<= 1);
	memset(T, 0x3f, sizeof(T));
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), ps[a[i]] = i, T[i + M][i & 1] = a[i];
	for (int i = M; i; --i) for (int j = 0; j < 2; ++j) T[i][j] = min(T[i << 1][j], T[i << 1 | 1][j]);
	q.push(node(1, n, 1));
	while (!q.empty()) {
		node u = q.top(); q.pop();
		printf("%d %d ", a[u.s], a[u.t]);
		if (u.l < u.s) q.push(node(u.l, u.s - 1, u.c));
		if (u.t < u.r) q.push(node(u.t + 1, u.r, u.c));
		if (u.s + 1 < u.t) q.push(node(u.s + 1, u.t - 1, u.c ^ 1));
	} putchar('\n');
	return 0;
}