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;
const int N = 8e5 + 9, INF = 0x3f3f3f3f;

#define L (x<<1)
#define R (x<<1|1)
int mi[N][2], p[N], n, pp[N];
bool vis[N];

void update(int x) {
	mi[x][0] = p[mi[L][0]] < p[mi[R][0]] ? mi[L][0] : mi[R][0];
	mi[x][1] = p[mi[L][1]] < p[mi[R][1]] ? mi[L][1] : mi[R][1];
}

void Build (int x, int l, int r) {
	if (l == r) {
		if (l & 1) mi[x][1] = l, mi[x][0] = 0;
		else mi[x][0] = l, mi[x][1] = 0;
		return ;
	}
	int mid = (l + r) >> 1;
	Build(L, l, mid);
	Build(R, mid + 1, r);
	update(x);
}

int Query (int x, int l, int r, int ql, int qr, bool o) {
	if (ql > qr || ql > n) return INF;
	if (l == ql && r == qr) return mi[x][o];
	int mid = (l + r) >> 1;
	if (qr <= mid) return Query (L, l, mid, ql, qr, o);
	if (ql > mid) return Query (R, mid + 1, r, ql, qr, o);
	int al = Query(L, l, mid, ql, mid, o), ar = Query(R, mid + 1, r, mid + 1, qr, o);
	return p[al] < p[ar] ? al : ar;
}

struct it {
	int l, r, al, ar;
	it (int l, int r) : l(l), r(r) {
		al = Query(1, 1, n, l, r, l & 1), ar = Query(1, 1, n, al + 1, r, (l & 1) ^ 1);
	}
	bool operator < (const it &rhs) const { return p[al] > p[rhs.al]; }
};

priority_queue<it>Q;

int main () {
	scanf("%d", &n);
	p[0] = INF;
	for (int i = 1; i <= n; ++i) scanf("%d", &p[i]), pp[p[i]] = i;
	Build(1, 1, n);
	Q.push(it(1, n));
	int l, r, al, ar;
	while (!Q.empty()) {
		l = Q.top().l; r = Q.top().r; al = Q.top().al; ar = Q.top().ar; Q.pop();
		printf("%d %d ", p[al], p[ar]);
		if (l < al) Q.push(it(l, al - 1));
		if (ar < r) Q.push(it(ar + 1, r));
		if (al + 1 < ar) Q.push(it(al + 1, ar - 1));
	}
	return 0;
}