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 rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define pr pair<int, int>
#define x first
#define y second
using namespace std;

template<typename T>
void read(T& n){
	char ch; int sign = 1;
	while (!isdigit(ch = getchar())) if (ch == '-') sign = -1;
	n = ch - '0';
	while (isdigit(ch = getchar())) n = n * 10 + ch - '0';
	n *= sign;
}
typedef long long ll;
const int INF = 1e9 + 7;
const int N = 211111;
int n;
int a[N], pos[N], f[2][N][44];
struct node{
	int v, l, r;
	bool operator <(const node rhs) const{
		return v > rhs.v;
	}
};
priority_queue<node> heap;

void init(int idx){
	for (int i = 1; (1 << i) <= n; ++i)
		for (int j = 1; j + (1 << i) - 1 <= n; ++j)
			f[idx][j][i] = min(f[idx][j][i-1], f[idx][j+(1<<i-1)][i-1]);
}
int query(int idx, int l, int r){
	if (l > r||l <= 0||r > n) return INF;
	int k = 0; while((1ll << k) <= r - l + 1) k++; k--;
	return min(f[idx][l][k], f[idx][r-(1<<k)+1][k]);
}
void dfs(int l, int r){
	int t1 = pos[query(l % 2, l, r)], t2 = pos[query(l % 2 == 0, t1 + 1, r)];
	printf("%d %d ", a[t1], a[t2]);
	heap.push((node){query(l % 2, l, t1 - 1), l, t1 - 1});
	heap.push((node){query((t1 + 1) % 2, t1 + 1, t2 - 1), t1 + 1, t2 - 1});
	heap.push((node){query((t2 + 1) % 2, t2 + 1, r), t2 + 1, r});
	while(!heap.empty()){
		node t = heap.top(); heap.pop();
		if (t.l <= t.r) dfs(t.l, t.r);
	}
}

int main(){
	read(n);
	memset(f, 127, sizeof(f));
	rep(i, 1, n){
		read(a[i]), pos[a[i]] = i;
		if (i % 2 == 0) f[0][i][0] = a[i];
		else f[1][i][0] = a[i];
	}
	init(0), init(1); dfs(1, n); puts("");
	return 0;
}