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<cstdio>
using namespace std;
const int N=200200,oo=1000000000;
int i,j,k,n,m,ch,Hn;
int a[N],ST[2][N][22],Lg2[N];
struct heap {
	int l,r,v;
	bool operator < (const heap &n) const {
		return a[v]<a[n.v];
	}
} H[N];
void R(int &x) {
	x=0;ch=getchar();
	while (ch<'0' || '9'<ch) ch=getchar();
	while ('0'<=ch && ch<='9') x=x*10+ch-'0',ch=getchar();
}
int get_min(int k,int l,int r) {
	int t=Lg2[r-l+1];
	int t1=ST[k][l][t],t2=ST[k][r-(1<<t)+1][t];
	if (a[t1]<a[t2]) return t1;
	return t2;
}
void S(int x,int y) {
	heap t=H[x];H[x]=H[y];H[y]=t;
}
void up(int x) {
	while (x>1 && H[x]<H[x>>1]) S(x,x>>1),x>>=1;
}
void down(int x) {
	while ((x<<1)<=Hn) {
		int k=x<<1;
		if (k<Hn && H[k|1]<H[k]) k|=1;
		if (H[k]<H[x]) S(x,k),x=k;
		else break;
	}
}
int main() {
	R(n);
	m=0;
	while ((1<<m+1)<=n) m++;
	for (i=0;i<=m;i++) Lg2[1<<i]=i;
	for (i=3;i<=n;i++) if (!Lg2[i]) Lg2[i]=Lg2[i-1];
	a[0]=oo;
	for (i=1;i<=n;i++) {
		R(a[i]);
		int t=i&1;
		ST[t][i][0]=i;
	}
	for (j=1;j<=m;j++)
		for (i=1;i<=n;i++) if (i+(1<<j)-1<=n)
			for (k=0;k<2;k++) {
				if (a[ST[k][i][j-1]]<a[ST[k][i+(1<<j-1)][j-1]]) ST[k][i][j]=ST[k][i][j-1];
				else ST[k][i][j]=ST[k][i+(1<<j-1)][j-1];
			}
	H[1].l=1;H[1].r=n;H[1].v=get_min(1,1,n);
	Hn=1;down(1);
	for (i=1;i<=n;i+=2) {
		heap t=H[1];
		H[1]=H[Hn--];
		down(1);
		int t1=t.v,t2=get_min((t.v&1)^1,t.v+1,t.r);
		printf("%d %d ",a[t1],a[t2]);
		if (t.l<t1-1) {
			Hn++;
			H[Hn].l=t.l;
			H[Hn].r=t1-1;
			H[Hn].v=get_min(H[Hn].l&1,H[Hn].l,H[Hn].r);
			up(Hn);
		}
		if (t1+1<t2-1) {
			Hn++;
			H[Hn].l=t1+1;
			H[Hn].r=t2-1;
			H[Hn].v=get_min(H[Hn].l&1,H[Hn].l,H[Hn].r);
			up(Hn);
		}
		if (t2+1<t.r) {
			Hn++;
			H[Hn].l=t2+1;
			H[Hn].r=t.r;
			H[Hn].v=get_min(H[Hn].l&1,H[Hn].l,H[Hn].r);
			up(Hn);
		}
	}
}