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 <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int sz=2e5+7;
int a[sz],n,pos[sz];
int xds[sz*4][2];
void build(int nd,int L,int r)
{	int mid=(L+r)/2;
	if(L==r)
	{	xds[nd][0]=xds[nd][1]=sz;
		xds[nd][L%2]=a[L]; return ;
	}
	build(nd*2,L,mid); build(nd*2+1,mid+1,r);
	for(int ii=0;ii<2;ii++)
		xds[nd][ii]=min(xds[nd*2][ii],xds[nd*2+1][ii]);
}
int ask(int nd,int L,int r,int x,int y,int k)
{	int mid=(L+r)/2;
	if(L>y||r<x) return sz;
	if(L>=x&&r<=y) return xds[nd][k];
	return min(ask(nd*2,L,mid,x,y,k),ask(nd*2+1,mid+1,r,x,y,k));
}
struct ST
{	int l,r,v;
	ST(int aa=0,int bb=0,int cc=0):l(aa),r(bb),v(cc){}
	bool operator < (const ST& rsh) const
	{
		return v>rsh.v;
	}
};
priority_queue<ST> Q;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){scanf("%d",&a[i]); pos[a[i]]=i;}
	build(1,1,n);
	while(!Q.empty()) Q.pop();
	int v=xds[1][1];
	Q.push(ST(1,n,v));
	for(int i=2;i<=n;i+=2)
	{	ST t=Q.top(); Q.pop();
		v=ask(1,1,n,t.l,t.r,t.l%2);
		printf("%d ",v);
		int p=pos[v];
		v=ask(1,1,n,p+1,t.r,(p+1)%2);
		printf("%d%c",v,i<n?' ':'\n');
		int pp=pos[v];
		if(t.l<p-1)
		{	v=ask(1,1,n,t.l,p-1,t.l%2);
			Q.push(ST(t.l,p-1,v));
		}
		if(p+1<pp-1)
		{	v=ask(1,1,n,p+1,pp-1,(p+1)%2);
			Q.push(ST(p+1,pp-1,v));
		}
		if(pp+1<t.r)
		{	v=ask(1,1,n,pp+1,t.r,(pp+1)%2);
			Q.push(ST(pp+1,t.r,v));
		}
	}
	return 0;
}