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;
#define ll long long
#define all(V) V.begin(),V.end()
#define MOD 1000000007

int R[200010], T[200010];
vector<int> es(524288, INT32_MAX), os = es;
vector<int> G[200010];

int smin(bool V, int& s, int& t, int k = 1, int l = 0, int r = 262143) {
	if (t < l || r < s) {
		return INT32_MAX;
	}
	if (s <= l && r <= t) {
		if (V)return os[k];
		return es[k];
	}
	int lv = smin(V, s, t, k * 2, l, (l + r) / 2);
	int rv = smin(V, s, t, k * 2 + 1, (l + r) / 2 + 1, r);
	return min(lv, rv);
}

void segfy(vector<int>& V) {
	for (int i = 262143;i > 0;i--) {
		V[i] = min(V[i * 2], V[i * 2 + 1]);
	}
}

void ans(int s, int t, bool b, int c) {
	if (s > t)
		return;
	int lv = smin(b, s, t);
	int l = R[lv];
	int rv = smin(!b, l, t);
	int r = R[rv];

	G[c].push_back(lv);
	T[lv] = rv;
	T[rv] = lv;
	ans(s, l - 1, b, lv);
	ans(l + 1, r - 1, !b, lv);
	ans(r + 1, t, b, lv);
}

int main() {
	int N, p;
	cin >> N;
	for (int i = 1;i <= N;i++) {
		cin >> p;
		if (i & 1) {
			os[i + 262144] = p;
			es[i + 262144] = INT32_MAX;
		}
		else {
			es[i + 262144] = p;
			os[i + 262144] = INT32_MAX;
		}
		R[p] = i;
	}
	segfy(es);segfy(os);

	ans(1, N, 1, 0);

	priority_queue<int, vector<int>, greater<int>> Q;
	Q.push(0);
	while (!Q.empty()) {
		p = Q.top();
		if (p)cout << p << " " << T[p] << " ";
		Q.pop();
		for (int i : G[p]) {
			Q.push(i);
		}
	}
	cout << endl;
}