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
#include<bits/stdc++.h>
#define MN 200010
struct que{
	int val,l,r;
};
bool operator<(que a,que b)
{
	return a.val>b.val;
}
std::priority_queue<que> pq;
int n,p[MN],ha[MN];
int jump[MN][18],v[MN][18];
int serch(int l,int r)
{
	int now=n;
	for(int i=17;i>=0&&l<=r;i--)
	{
		if(!jump[l][i]||jump[l][i]>r+1) continue;
		now=std::min(now,v[l][i]);
		l=jump[l][i];
	}
	return now;
}
void ins(int l,int r)
{
	if(l>r) return ;
	que x;
	x.l=l;x.r=r;
	x.val=serch(l,r);
	pq.push(x);
}
void init()
{
	p[n+1]=p[n+2]=n+2;
	for(int i=1;i<=n+1;i++) jump[i][0]=i+2,v[i][0]=p[i];
	for(int i=1;i<=17;i++)
	{
		for(int j=1;j<=n+1;j++)
		{
			jump[j][i]=jump[jump[j][i-1]][i-1];
			v[j][i]=std::min(v[j][i-1],v[jump[j][i-1]][i-1]);
		}
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&p[i]),ha[p[i]]=i;
	init();
	ins(1,n);
	while(!pq.empty())
	{
		que x=pq.top();
		pq.pop();
		int l=x.l,r=x.r,v1=x.val,v2;
		v2=serch(ha[v1]+1,r+1);
		ins(l,ha[v1]-1);
		ins(ha[v1]+1,ha[v2]-1);
		ins(ha[v2]+1,r);
		printf("%d %d ",v1,v2);
	}
}