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 L long long
#define pb push_back
#define pi pair<int,int>
#define pii pair<pair<int,int>,int>
#define aa first
#define bb second
#define xx aa.aa
#define yy aa.bb
#define zz bb
#define mp make_pair
#define mpp(a,b,c) mp(mp(a,b),c)
using namespace std;
int n,m,a[200010],b[200010],x[200010],f[600000][2],p;
set<pii> w;
pii u;
inline void modify(int i,int j,int k,int x,int y,int p)
{
	if(j==k)
	  f[i][y]=p;
	else
	  {
	   if(x<=(j+k>>1))
	     modify(i<<1,j,j+k>>1,x,y,p);
	   else
	     modify(i<<1|1,(j+k>>1)+1,k,x,y,p);
	   f[i][y]=min(f[i<<1][y],f[i<<1|1][y]);
	  }
}
inline int minn(int i,int j,int k,int l,int r,int x)
{
	if(l<=j && k<=r)
	  return f[i][x];
	else
	  {
	   int p=1e9;
	   if(l<=(j+k>>1))
	     p=min(p,minn(i<<1,j,j+k>>1,l,r,x));
	   if(r>(j+k>>1))
	     p=min(p,minn(i<<1|1,(j+k>>1)+1,k,l,r,x));
	   return p;
	  }
}
inline void del(int i)
{
	x[++m]=i;
	modify(1,1,p,b[i],b[i]&1,1e9);
}
inline void ins(int l,int r)
{
	if(l<=r)
	  w.insert(mpp(minn(1,1,p,l,r,l&1),l,r));
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int i,j,l,r;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	  scanf("%d",&a[i]);
	for(i=1;i<=n;i++)
	  b[a[i]]=i;
	for(p=1;p<n;p<<=1);
	for(i=1;i<2*p;i++)
	  f[i][0]=f[i][1]=1e9;
	for(i=1;i<=n;i++)
	  modify(1,1,p,i,i&1,a[i]);
	ins(1,n);
	while(!w.empty())
	  {
	   u=*w.begin();
	   w.erase(u);
	   i=u.xx;
	   j=minn(1,1,p,b[i],u.zz,u.zz&1);
	   del(i);
	   del(j);
	   ins(u.yy,b[i]-1);
	   ins(b[i]+1,b[j]-1);
	   ins(b[j]+1,u.zz);
	  }
	for(i=1;i<=n;i++)
	  printf("%d ",x[i]);
	return 0;
}