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
#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 2e5 + 100;

struct IDX{
	int P; vector<int> val;
	IDX() {}
	IDX(vector<int> nr) {
		int n = SZ(nr);
		for(P=1; P<n; P<<=1);
		val = vector<int>(2*P, INF);
		for(int i=0; i<P; i++) val[P+i] = (i<n ? nr[i] : INF);
		for(int i=P-1; i>=1; i--) val[i] = min(val[i*2], val[i*2+1]);
	}
	int getMin(int a, int b) {
		int res = INF;
		for(a+=P, b+=P; a<=b; a>>=1, b>>=1) {
			if(a%2==1) res = min(res, val[a++]);
			if(b%2==0) res = min(res, val[b--]);
		}
		return res;
	}
};

IDX idx[2];
int N, Nr[MAX_N], Re[MAX_N];
struct NODE{
	int l, r, a, b;
	NODE(int lv, int rv) : l(lv), r(rv) {
		a = Re[idx[l%2].getMin(l/2, (r-1)/2)];
		b = Re[idx[r%2].getMin((a+1)/2, r/2)];
	}
	pi getLR() const {return pi(l, r);}
	pi getAB() const {return pi(a, b);}
	bool operator<(const NODE &o) const{return Nr[a] > Nr[o.a];}
};
int main() {
	vector<int> nr[2];
	cin >> N; for(int i=0; i<N; i++) scanf("%d", &Nr[i]), Re[Nr[i]] = i, nr[i%2].push_back(Nr[i]);
	for(int k=0; k<2; k++) idx[k] = IDX(nr[k]);
	priority_queue<NODE> Q;
	Q.emplace(0, N-1);
	while(!Q.empty()) {
		int l, r; tie(l, r) = Q.top().getLR(); 
		int a, b; tie(a, b) = Q.top().getAB(); Q.pop();
		printf("%d %d ", Nr[a], Nr[b]);
		pi val[3] = {pi(l, a-1), pi(a+1, b-1), pi(b+1, r)};
		for(int k=0; k<3; k++) {
			int x, y; tie(x, y) = val[k];
			if(x > y) continue;
			Q.emplace(x, y);
		}
	}
	return 0;
}
