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;

typedef long long ll;
typedef pair < int, int > ii;

const int N = 2e5 + 5;

int n;
int a[N];

class tree{ public:
	ii t[N << 1];
	void init() {
		for(int i = 1; i < (N << 1); i++)
			t[i] = {1e9, -1};
	}
	void add(int i, ii x) {
		t[i += N] = x;
		while(i > 1) {
			i >>= 1;
			t[i] = min(t[i + i], t[i + i + 1]);
		}
	}
	ii get(int l, int r) {
		ii res = {1e9, -1};
		for(l += N, r += N; l <= r; l = (l + 1) >> 1, r = (r - 1) >> 1) {
			if(l & 1) res = min(res, t[l]);
			if(~r & 1) res = min(res, t[r]);
		}
		return res;
	}
}odd, even;

int cnt = 1;
set < ii > s[N];
map < ii, ii > M;

void solve(int l, int r) {
	if(l > r)
		return;
	int i, j;
	if(l & 1) {
		i = odd.get(l, r).second;
		j = even.get(i + 1, r).second;
	}
	else {
		i = even.get(l, r).second;
		j = odd.get(i + 1, r).second;
	}
	solve(l, i - 1);
	solve(i + 1, j - 1);
	solve(j + 1, r);
	M[{l, r}] = {i, j};

}

ii get(int l, int r) {
	ii x = M[{l, r}];
	return {a[x.first], a[x.second]};
}

int main() {

	odd.init();
	even.init();

	scanf("%d", &n);

	for(int i = 1; i <= n; i++) {
		scanf("%d", a + i);
		if(i & 1)
			odd.add(i, {a[i], i});
		else
			even.add(i, {a[i], i});
	}

	solve(1, n);

	set < pair < ii, ii > > s;

	int i, j;
	tie(i, j) = M[{1, n}];

	s.insert({{a[i], a[j]}, {1, n}});

	while(s.size()) {
		auto x = *s.begin();
		s.erase(s.begin());
		printf("%d %d ", x.first.first, x.first.second);
		int l, r;
		tie(l, r) = x.second;
		tie(i, j) = M[{l, r}];
		if(l <= i - 1)
			s.insert({get(l, i - 1), {l, i - 1}});
		if(i + 1 <= j - 1)
			s.insert({get(i + 1, j - 1), {i + 1, j - 1}});
		if(j + 1 <= r)
			s.insert({get(j + 1, r), {j + 1, r}});
	}

	puts("");

    return 0;

}