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>
#define N 400005
using namespace std;
int n,a[N],b[N*4][2],fst[N],to[N],nxt[N],l,cnt;
int cp(int x,int y)
{
	return a[x]<a[y]?x:y;
}
void up(int k)
{
	for (int i=0;i<=1;i++)
		b[k][i]=cp(b[k<<1][i],b[k<<1|1][i]);
}
void build(int k,int l,int r)
{
	if (l==r)
	{
		b[k][l&1]=l;
		return;
	}
	int mid=l+r>>1;
	build(k<<1,l,mid);build(k<<1|1,mid+1,r);
	up(k);
}
int qry(int k,int l,int r,int x,int y,int p)
{
	if (x<=l&&r<=y)
		return b[k][p];
	int mid=l+r>>1,ans=0;
	if (x<=mid) ans=cp(ans,qry(k<<1,l,mid,x,y,p));
	if (y>mid) ans=cp(ans,qry(k<<1|1,mid+1,r,x,y,p));
	return ans;
}
void link(int x,int y)
{
	to[++l]=y;nxt[l]=fst[x];fst[x]=l;
}
struct T
{
	int x,y;
}v[N];
bool operator<(T a,T b)
{
	return a.x>b.x;
}
void Get(int f,int l,int r)
{
	if (l>r) return;
	int t=l&1;
	int x=qry(1,1,n,l,r,t);
	int y=qry(1,1,n,x+1,r,t^1);
	int tmp=++cnt;
	v[tmp]=(T){a[x],a[y]};
	link(f,tmp);
	Get(tmp,l,x-1);
	Get(tmp,x+1,y-1);
	Get(tmp,y+1,r);
}

priority_queue<T>q;
int main()
{
	scanf("%d",&n);
	a[0]=10000000;
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		//scanf("%d",&b[i]);
	}
	build(1,1,n);
	cnt=1;
	Get(1,1,n);
	
	for (int i=fst[1];i;i=nxt[i])
		q.push((T){v[to[i]].x,to[i]});
	while(q.size())
	{
		int t=q.top().y;
		q.pop();
		printf("%d %d ",v[t].x,v[t].y);
		for (int i=fst[t];i;i=nxt[i])
			q.push((T){v[to[i]].x,to[i]});
	}
	puts("");
}