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 mod 1000000007
#define mod998 998244353
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;

int N, p[200000];
pair<int,int> tree[1 << 19][2];
priority_queue<pair<pair<int, int>, pair<int, int>>, vector<pair<pair<int, int>, pair<int, int>>>, greater<pair<pair<int, int>, pair<int, int>>>>q;
queue<int>res;

pair<int, int> calc(int l, int r, int p, int q, int k) {
	if (r < p || q < l)return mkp(0xE869120, -1);
	if (p <= l&&r <= q)return tree[k][p & 1];
	return min(calc(l, (l + r) / 2, p, q, k * 2), calc((l + r) / 2 + 1, r, p, q, k * 2 + 1));
}

void dfs(int l, int r) {
	if (l > r)return;
	int L = calc(0, (1 << 18) - 1, l, r, 1).second;
	int R = calc(0, (1 << 18) - 1, L + 1, r, 1).second;
	q.push(mkp(mkp(p[L], p[R]), mkp(L + 1, R - 1)));
	dfs(l, L - 1);
	dfs(R + 1, r);
}

int main() {
	cin >> N;
	for (int i = 0; i < N; ++i) {
		cin >> p[i];
		tree[(1 << 18) + i][i & 1] = mkp(p[i], i);
		tree[(1 << 18) + i][!(i & 1)] = mkp(0xE869120, -1);
	}
	for (int i = (1 << 18) - 1; i; --i) {
		tree[i][0] = min(tree[i * 2][0], tree[i * 2 + 1][0]);
		tree[i][1] = min(tree[i * 2][1], tree[i * 2 + 1][1]);
	}
	q.push(mkp(mkp(-1, -1), mkp(0, N - 1)));
	while (!q.empty()) {
		res.push(q.top().first.first);
		res.push(q.top().first.second);
		int l = q.top().second.first;
		int r = q.top().second.second;
		q.pop();
		dfs(l, r);
	}
	res.pop();
	res.pop();
	while (!res.empty()) {
		cout << res.front() << sp;
		res.pop();
	}
	cout << endl;
}