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>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#ifdef _DEBUG_
	#define debug(...) printf(__VA_ARGS__)
#else
	#define debug(...) (void)0
#endif
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;

const int LOGN = 20;
const int MAXN = 200000 + 10;

int a[MAXN], lg2[MAXN];
PII odd[LOGN][MAXN], even[LOGN][MAXN];

PII query(int l, int r, int t) {
	assert(l <= r);
	int k = lg2[r-l+1];
	if(t ^ (l%2))
		return min(odd[k][l], odd[k][r-(1<<k)+1]);
	else
		return min(even[k][l], even[k][r-(1<<k)+1]);
}

int main() {
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; i++) {
		scanf("%d", a+i);
		odd[0][i] = MP(a[i], i), even[0][i] = MP(n+1, i);
		if(i%2 == 0)	swap(odd[0][i], even[0][i]);
	}
	for(int i=1, l=1; i<LOGN; i++, l<<=1) {
		for(int j=0; j+l<n; j++) {
			odd[i][j] = min(odd[i-1][j], odd[i-1][j+l]);
			even[i][j] = min(even[i-1][j], even[i-1][j+l]);
		}
	}
	for(int i=1, lg=0; i<=n; i++) {
		if((1<<(lg+1)) < i)	lg++;
		lg2[i] = lg;
	}

	priority_queue<pair<PII, PII>, vector<pair<PII,PII>>, greater<pair<PII, PII> > > pq;
	VI ans;
	pq.push(MP(query(0, n-1, 0), MP(0, n-1)));
	while(!pq.empty()) {
		auto p = pq.top();	pq.pop();
		int l = p.S.F, r = p.S.S, i = p.F.S;
		// printf("%d %d %d\n", l, r, i);
		assert(r <= n);
		assert(l!=r);
		if(l>r)	continue;
		auto tmp = query(i, r, 1);
		int j = tmp.S;
		ans.PB(p.F.F);
		ans.PB(tmp.F);
		// printf("(i, j) = (%d, %d)\n", i, j);
		if(l <= i-1)	pq.push(MP(query(l, i-1, 0), MP(l, i-1)));
		if(i+1 <= j-1)	pq.push(MP(query(i+1, j-1, 0), MP(i+1, j-1)));
		if(j+1 <= r)	pq.push(MP(query(j+1, r, 0), MP(j+1, r)));
	}

	for(int i=0; i<SZ(ans); i++)	printf("%d%c", ans[i], " \n"[i==SZ(ans)-1]);
}