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 <algorithm>
#include <queue> 
#define il inline
#define N 200001
using namespace std;

int T,n,a[N],b[N],pos[N];
int t[2][4*N];
struct node
{
	int a,b,x,y,l,r;
};
il bool operator < (node i,node j){return i.a>j.a;}
priority_queue<node> h;

il char gc()
{
    static char now[1<<20],*S,*T;
    if (T==S)
    {
        T=(S=now)+fread(now,1,1<<20,stdin);
        if (T==S) return EOF;
    }
    return *S++;
}

il int read()
{
	int res=0;
	char c;
	while ((c=gc())<'0'||c>'9');
	res=(c^48);
	while ((c=gc())>='0'&&c<='9') res=(res<<3)+(res<<1)+(c^48);
	return res;
}

il void build(int k,int l,int r)
{
	if (l==r){t[0][k]=b[l],t[1][k]=a[l];return;}
	int mid=(l+r)>>1;
	build(k<<1,l,mid),build(k<<1|1,mid+1,r);
	t[0][k]=min(t[0][k<<1],t[0][k<<1|1]),t[1][k]=min(t[1][k<<1],t[1][k<<1|1]);
}

il int query(int id,int k,int l,int r,int x,int y)
{
	if (l>=x&&r<=y) return t[id][k];
	int mid=(l+r)>>1,res=2e8;
	if (x<=mid) res=min(res,query(id,k<<1,l,mid,x,y));
	if (y>mid) res=min(res,query(id,k<<1|1,mid+1,r,x,y));
	return res;
}

il void work(int l,int r)
{
	if (l>r) return;
	int x=query(l&1,1,1,n,l,r),X=pos[x],y=query(l&1^1,1,1,n,X,r),Y=pos[y];
	node res=(node){x,y,X,Y,l,r};
	h.push(res);
} 

int main()
{
	n=read();
	int i,x,y,l,r,X,Y;
	node now;
	for (i=1; i<=n; i++)
	{
		if (i&1) pos[a[i]=read()]=i,b[i]=1e8;
		else pos[b[i]=read()]=i,a[i]=1e8;
	}
	build(1,1,n),work(1,n);
	
	while (!h.empty())
	{
		node now=h.top(); h.pop();
		printf("%d %d ",now.a,now.b);
		work(now.l,now.x-1),work(now.x+1,now.y-1),work(now.y+1,now.r);
	}
	
	return 0;
}