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;
 
int read() {
    int f = 1, x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')   {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    x *= f; return x;
}
 
/*============ Header Template ============*/

const int N = 200005;
int a[N], f[N][20], idx[N];
int MIN(int x,int y) {
	return a[x] < a[y] ? x : y;
}
int findmin(int x, int y) {
	int z = idx[y - x + 1];
	return MIN(f[x][z], f[y - (1 << z) + 1][z]);
}
struct sav {
	int l, r, x, y;
	sav (const int a = 0, const int b = 0) : l(a), r(b), x(findmin(a, b)), y(findmin(x + 1, b + 1)){}
};
bool operator < (sav x, sav y) {
	return a[x.x] > a[y.x];
}
priority_queue<sav> q;
int main(){
	int n = read();
	a[0] = n + 1; idx[0] = -1;
	for (int i = 1; i <= n; i ++) idx[i] = idx[i >> 1] + 1, f[i][0] = f[i][1] = i;
	for (int i = 1; i <= n; i ++) a[i] = read();
	for (int i = n; i; i --)
		for (int j = 2; i + (1 << j) - 1 <= n + 1; j ++)
			f[i][j] = MIN(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
	q.push(sav(1, n));
	for (; !q.empty();){
		sav now = q.top(); q.pop();
		printf("%d %d ", a[now.x], a[now.y]);
		if (now.l < now.x) q.push(sav(now.l, now.x - 1));
		if (now.x + 1 < now.y) q.push(sav(now.x + 1, now.y - 1));
		if (now.y < now.r) q.push(sav(now.y + 1, now.r));
	}
	return 0;
}