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;
using P = pair<int, int>;
using Pi = pair<P,int>;
#define rep(i,n) for(int i=0;i<n;i++)
const int mx = 200005;
int n, q[mx], p, c;
vector<int> ch[mx];
P ans[mx];
priority_queue<Pi, vector<Pi>, greater<Pi>> qu;
struct SegTree{
	int sz;
	P ide = P(1e9,0);
	vector<P> dat;
	SegTree(int n){
		for(sz = 2; sz < n; sz *= 2);
		dat.assign(sz*2, ide);
	}
	void set(int x, P n){
		dat[x += sz] = n;
		while(x /= 2) dat[x] = min(dat[x*2], dat[x*2+1]);
	}
	P query(int a, int b, int k = 1, int l = 0, int r = -1){
		if(r == -1) r = sz;
		if(r <= a || b <= l) return ide;
		if(a <= l && r <= b) return dat[k];
		return min(query(a, b, k*2, l, (l+r)/2), query(a, b, k*2+1, (l+r)/2, r));
	}
} sg[2] = {SegTree(mx), SegTree(mx)};

void solve(int s, int v, int pr){
	if(s == v) return;
	P ss = sg[s&1].query(s, v);
	P vv = sg[s&1^1].query(ss.second+1, v+1);
	if(c) ch[pr].push_back(c);
	ans[pr = c++] = P(ss.first,vv.first);
	solve(s, ss.second, pr);
	solve(ss.second+1, vv.second, pr);
	solve(vv.second+1, v, pr);
}
int main(){
	scanf("%d", &n);
	rep(i,n){
		scanf("%d", &p);
		sg[i&1].set(i,P(p,i));
	}
	solve(0,n,0);
	qu.push(Pi(ans[0],0));
	while(!qu.empty()){
		auto it = qu.top(); qu.pop();
		printf("%s%d %d", (it.second ? " " : ""), it.first.first, it.first.second);
		for(auto t: ch[it.second]) qu.push(Pi(ans[t],t));
	}
	puts("");
}