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 fi first
#define se second
#define mp make_pair
using namespace std;

typedef pair <int, int> pii;
typedef pair <pii, int> piii;

const int INF = 0x3f3f3f3f;

int n;
int a[200010];
int f1[200010][20], f2[200010][20];
int pos[200010];
pii val[200010];
int tot = 0;
priority_queue <piii, vector <piii>, greater <piii> > q;
vector <int> from[200010];

void get_f(){
	for (int i = 0; i < n; i++){
		if (i & 1) f1[i][0] = a[i], f2[i][0] = INF;
		else f2[i][0] = a[i], f1[i][0] = INF;
	}
	for (int j = 1; j < 20; j++){
		for (int i = 0; i < n; i++){
			if (i + (1 << j) - 1 > n) continue;
			f1[i][j] = min(f1[i][j - 1], f1[i + (1 << j - 1)][j - 1]);
			f2[i][j] = min(f2[i][j - 1], f2[i + (1 << j - 1)][j - 1]);
		}
	}
}

int get_min1(int l, int r){
	int k = log(r - l + 1) / log(2);
	return min(f1[l][k], f1[r - (1 << k) + 1][k]);
}

int get_min2(int l, int r){
	int k = log(r - l + 1) / log(2); 
	return min(f2[l][k], f2[r - (1 << k) + 1][k]);
}

int dfs(int l, int r){
	if (l > r) return -1;
	int x, y, m1, m2;
	if (l & 1){
		x = get_min1(l, r), m1 = pos[x];
		y = get_min2(m1, r), m2 = pos[y];
	} else {
		x = get_min2(l, r), m1 = pos[x];
		y = get_min1(m1, r), m2 = pos[y];
	}
	int now = tot++;
	val[now] = mp(x, y);
	from[now].push_back(dfs(l, m1 - 1));
	from[now].push_back(dfs(m1 + 1, m2 - 1));
	from[now].push_back(dfs(m2 + 1, r));
	return now;
}

int main(){
	scanf("%d", &n);
	for (int i = 0; i < n; i++){
		scanf("%d", &a[i]);
		pos[a[i]] = i;
	}
	get_f();
	int s = dfs(0, n - 1);
	q.push(mp(val[s], s));
	while (!q.empty()){
		piii t = q.top(); q.pop();
		printf("%d %d ", t.fi.fi, t.fi.se);
		int x = t.se;
		for (int i = 0; i < from[x].size(); i++){
			int v = from[x][i];
			if (v == -1) continue;
			q.push(mp(val[v], v));
		}
	}
	printf("\n");
	return 0;
}