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>
#include<iostream>
#include<queue>
#include<cstring>
#define maxn 400010
using namespace std;
int a[maxn],n,i,j,g[maxn][18],gg[maxn][18],h[maxn][18],hh[maxn][18],head,tail=1,log[maxn],y,x;
struct type
{
	int l,r,x;
}t;
bool operator < (type x,type y)
{
	return x.x>y.x;
}
priority_queue<type>f;
int get(int l,int r)
{
	if(gg[l][log[(r-l+1)/2]]<gg[r-(1<<log[r-l+1])+1][log[(r-l+1)/2]])return hh[l][log[(r-l+1)/2]];else return hh[r-(1<<log[r-l+1])+1][log[(r-l+1)/2]];
}
int main()
{
	scanf("%d",&n);
	log[0]=-1;
	for(i=1;i<=n;i++)
		log[i]=log[i>>1]+1;
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	memset(g,0x3f,sizeof(g));
	memset(gg,0x3f,sizeof(gg));
	for(i=1;i<n;i++)
	{
		g[i][0]=a[i+1];
		h[i][0]=i+1;
	}
	for(i=1;i<=n;i++)
	{
		gg[i][0]=a[i];
		hh[i][0]=i;
	}
	for(j=1;j<=17;j++)
		for(i=1;i<=n;i++)
		{
			if(g[i][j-1]<g[i+(1<<j)][j-1])
			{
				g[i][j]=g[i][j-1];
				h[i][j]=h[i][j-1];
			}else
			{
				g[i][j]=g[i+(1<<j)][j-1];
				h[i][j]=h[i+(1<<j)][j-1];
			}
			if(gg[i][j-1]<gg[i+(1<<j)][j-1])
			{
				gg[i][j]=gg[i][j-1];
				hh[i][j]=hh[i][j-1];
			}else
			{
				gg[i][j]=gg[i+(1<<j)][j-1];
				hh[i][j]=hh[i+(1<<j)][j-1];
			}
		}
	f.push((type){1,n,a[get(1,n)]});
	for(i=1;i<=n/2;i++)
	{
		t=f.top();
		f.pop();
		x=get(t.l,t.r);
		printf("%d ",t.x);
		if(g[x][log[(t.r-x+1)/2]]<g[t.r-(1<<log[t.r-x+1])+1][log[(t.r-x+1)/2]])y=h[x][log[(t.r-x+1)/2]];else y=h[t.r-(1<<log[t.r-x+1])+1][log[(t.r-x+1)/2]];
		printf("%d ",a[y]);
		if(t.l<x)f.push((type){t.l,x-1,a[get(t.l,x-1)]});
		if(x<y-1)f.push((type){x+1,y-1,a[get(x+1,y-1)]});
		if(y+1<t.r)f.push((type){y+1,t.r,a[get(y+1,t.r)]});
	}
}