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 <queue>
using namespace std;

#define N 200050
#define INF 1000000007
int a[N];

int mn[2][N*8],pos[2][N*8];

#define ls p<<1
#define rs (p<<1)|1
void setTree(int p,int l,int r)
{
	if(l==r)
	{
		for(int i=0;i<2;i++)
			mn[i][p]=INF,pos[i][p]=l;
		(l&1)? mn[1][p]=a[l]: mn[0][p]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	setTree(ls,l,mid);
	setTree(rs,mid+1,r);
	for(int i=0;i<2;i++)
	{
		int tmp= mn[i][ls]<mn[i][rs]? ls: rs;
		mn[i][p]=mn[i][tmp],pos[i][p]=pos[i][tmp];
	}
}

int query(int p,int l,int r,int gl,int gr,int tp)
{
	if(l==gl && r==gr)
	{
		if(l==r)
			return (l&1)==tp? l: -1;
		else
			return pos[tp][p];
	}
	int mid=(l+r)>>1;
	if(gr<=mid) return query(ls,l,mid,gl,gr,tp);
	else if(gl>mid) return query(rs,mid+1,r,gl,gr,tp);
	else
	{
		int tl=query(ls,l,mid,gl,mid,tp);
		int tr=query(rs,mid+1,r,mid+1,gr,tp);
		if(tl==-1) return tr;
		else if(tr==-1) return tl;
		else return a[tl]<a[tr]? tl: tr;
	}
}

struct Node{int mnv,l,r;};
bool operator<(const Node &a,const Node &b){return a.mnv>b.mnv;}
priority_queue<Node> pq;

int whr[N];
int ans[N],acnt;
int main()
{
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		whr[a[i]]=i;
	}
	
	setTree(1,1,n);
	pq.push((Node){a[query(1,1,n,1,n,1)],1,n});
	for(int i=2;i<=n;i+=2)
	{
		Node nd=pq.top();pq.pop();
		ans[++acnt]=nd.mnv;
		int pos=whr[nd.mnv];
		int rp=query(1,1,n,pos+1,nd.r,(pos+1)&1);
		ans[++acnt]=a[rp];
		if(pos>nd.l)
		{
			pq.push((Node){a[query(1,1,n,nd.l,pos-1,nd.l&1)],nd.l,pos-1});
		}
		if(rp>pos+1)
		{
			pq.push((Node){a[query(1,1,n,pos+1,rp-1,(pos+1)&1)],pos+1,rp-1});
		}
		if(nd.r>rp)
		{
			pq.push((Node){a[query(1,1,n,rp+1,nd.r,(rp+1)&1)],rp+1,nd.r});
		}
	}
	for(int i=1;i<=n;i++)
		printf("%d%c",ans[i],i<n?' ':'\n');
}