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<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
using namespace std;
typedef long long LL;
int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}
const int N=2e5+100;
int Log[N],p[N],pos[N];
struct ST{
	int mi[20][N];
	inline void build(int n,int o) {
		for (int i=1;i<=n;i++)
			mi[0][i]=(i&1)==o?p[i]:n+1;
		for (int t=1;t<20;t++)
			for (int i=n-(1<<t)+1;i>0;i--)
				mi[t][i]=min(mi[t-1][i],mi[t-1][i+(1<<(t-1))]);
	}
	inline int query(int l,int r) {
		int s=Log[r-l+1];
		return min(mi[s][l],mi[s][r-(1<<s)+1]);
	}
}T[2];
struct seg{
	int l,r,L,R;
	seg() {}
	seg(int _l,int _r) {
		l=_l,r=_r;
		L=pos[T[l&1].query(l,r)];
		R=pos[T[~L&1].query(L+1,r)];
	}
	inline bool operator < (const seg &b) const { return p[L]>p[b.L]; };
};
int main()
{
	int n=gi(),i;
	for (Log[0]=-1,i=1;i<=n;i++) pos[p[i]=gi()]=i,Log[i]=Log[i>>1]+1;
	T[0].build(n,0),T[1].build(n,1);
	priority_queue<seg>q;seg t;
	q.push(seg(1,n));
	while (!q.empty()) {
		t=q.top();q.pop();
		printf("%d %d ",p[t.L],p[t.R]);
		if (t.l!=t.L) q.push(seg(t.l,t.L-1));
		if (t.L+1<t.R) q.push(seg(t.L+1,t.R-1));
		if (t.R!=t.r) q.push(seg(t.R+1,t.r));
	}
	return 0;
}