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;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int oo = 1e9;
const int MOD = 1000000007;
const int BASE = 26;
const int N = 202010;
const int MX = 200000;
#define x first
#define y second
#define pb push_back
#define mp make_pair

int seg[2][4 * N], n, p[N], bk[N];
void build(int n , int s , int e) {
	if (s == e) {
		seg[(s & 1) ^ 1][n] = oo;
		seg[(s & 1)][n] = p[s];
		return;
	}
	build(2 * n, s, (s + e) / 2);
	build(2 * n + 1, (s + e) / 2 + 1, e);
	seg[0][n] = min(seg[0][2 * n], seg[0][2 * n + 1]);
	seg[1][n] = min(seg[1][2 * n], seg[1][2 * n + 1]);
}
int get(int type, int n , int s , int e, int l , int r) {
	if (s > r || e < l)return oo;
	if (s >= l && e <= r)return seg[type][n];
	return min(get(type, 2 * n, s, (s + e) / 2, l, r), get(type, 2 * n + 1, (s + e) / 2 + 1, e, l, r));
}
struct inv {
	int l , r , x , y;
	inv(int _l , int _r) {
		l = _l;
		r = _r;
		x = get(l & 1, 1, 1, n, l, r);
		y = get((l & 1) ^ 1, 1, 1, n, bk[x], r);
	}
	bool operator<(const inv &r) const {
		if (x != r.y)
			return x > r.x;
		return y > r.y;
	}
};
vector<int> ans;
priority_queue<inv> q;

void push(int x , int y) {
	if (x > y)return;
	q.push(inv(x, y));
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &p[i]);
		bk[p[i]] = i;
	}
	build(1, 1, n);
	q.push(inv(1, n));
	while (q.size()) {
		inv f = q.top();
		q.pop();
		ans.pb(f.x);
		ans.pb(f.y);
		push(f.l, bk[f.x] - 1);
		push(bk[f.x] + 1, bk[f.y] - 1);
		push(bk[f.y] + 1, f.r);
	}
	for (int i = 0; i < ans.size(); ++i){
		if(i)printf(" ");
		printf("%d",ans[i]);
	}
	puts("");
	return 0;
}