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 N 200100

int n,L,R,x,y;
int d[2][N][20],a[N],pos[N],Log[N],t1[N],t2[N];
priority_queue<int,vector<int>,greater<int> > S;

void build() {
	for (int i=2;i<=n;i++) Log[i]=Log[i>>1]+1;
	for (int i=1;i<=n;i++) d[i&1][i][0]=a[i],d[(i&1)^1][i][0]=n+1;
	for (int i=1;i<=18;i++)
		for (int j=1;j+(1<<i)-1<=n;j++)
			for (int k=0;k<2;k++)
				d[k][j][i]=min(d[k][j][i-1],d[k][j+(1<<(i-1))][i-1]);
}

int query(int o,int l,int r) {
	//printf("%d %d %d\n",o,l,r);
	int len=Log[r-l+1];
	return min(d[o][l][len],d[o][r-(1<<len)+1][len]);
}

int query_begin(int x) {
	int ret=0;
	for (;x;x-=x&(-x)) ret=max(ret,t1[x]);
	return ret;
}

void begin_add(int x) {
	int tmp=x;
	for (;x<=n;x+=x&(-x)) t1[x]=max(t1[x],tmp);
}

int query_end(int x) {
	int ret=n+1;
	for (;x<=n;x+=x&(-x)) ret=min(ret,t2[x]);
	return ret;
}

void end_add(int x) {
	int tmp=x;
	for (;x;x-=x&(-x)) t2[x]=min(t2[x],tmp);
}

void Push(int l,int r) {
	if (l>r) return;
	S.push(query(l&1,l,r));
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]),pos[a[i]]=i;
	build();
	S.push(query(1,1,n));
	for (int i=1;i<=n;i++) t2[i]=n+1;
	while (!S.empty()) {
		x=S.top(); S.pop();
		L=query_begin(pos[x]-1);
		R=query_end(pos[x]+1);
		y=query((pos[x]&1)^1,pos[x]+1,R-1);
		printf("%d %d ",x,y);
		Push(L+1,pos[x]-1);
		Push(pos[x]+1,pos[y]-1);
		Push(pos[y]+1,R-1);
		begin_add(pos[x]); begin_add(pos[y]);
		end_add(pos[x]); end_add(pos[y]);
	}
	return 0;
}