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 <stdio.h>
#include <set>
#include <algorithm>
using namespace std;
int siz[524288],mnv[2][524288],mni[2][524288];
pair<int,int> query(int mod2,int id,int il,int ir,int l,int r)
{
	if (il>=l&&ir<=r)
		return make_pair(mnv[mod2][id],mni[mod2][id]);
	if (l>=ir||r<=il)
		return make_pair(1000000000,-1);
	return min(query(mod2,id<<1,il,(il+ir)>>1,l,r),query(mod2^(siz[id<<1]&1),(id<<1)^1,(il+ir)>>1,ir,l,r));
}
void update(int id)
{
	id+=262144;
	siz[id]=0;
	mnv[0][id]=1000000000;
	for (id>>=1;id;id>>=1)
	{
		siz[id]=siz[id<<1]+siz[(id<<1)^1];
		for (int i=0;i<2;++i)
		{
			mnv[i][id]=min(mnv[i][id<<1],mnv[i^(siz[id<<1]&1)][(id<<1)^1]);
			mni[i][id]=mnv[i][id<<1]<=mnv[i^(siz[id<<1]&1)][(id<<1)^1]?mni[i][id<<1]:mni[i^(siz[id<<1]&1)][(id<<1)^1];
		}
	}
}
int main()
{
	int n;
	scanf("%d",&n);
	for (int i=262144;i<524288;++i)
	{
		mnv[0][i]=mnv[1][i]=1000000000;
		mni[0][i]=mni[1][i]=i-262144;
		siz[i]=1;
	}
	for (int i=0;i<n;++i)
		scanf("%d",&mnv[0][262144+i]);
	for (int i=262143;i;--i)
	{
		siz[i]=siz[i<<1]+siz[(i<<1)^1];
		for (int j=0;j<2;++j)
		{
			mnv[j][i]=min(mnv[j][i<<1],mnv[j^(siz[i<<1]&1)][(i<<1)^1]);
			mni[j][i]=mnv[j][i<<1]<=mnv[j^(siz[i<<1]&1)][(i<<1)^1]?mni[j][i<<1]:mni[j^(siz[i<<1]&1)][(i<<1)^1];
		}
	}
	set<int> st;
	st.insert(n);
	for (int i=0;i<n/2;++i)
	{
		printf("%d ",mnv[0][1]);
		pair<int,int> id=query(1,1,0,262144,mni[0][1],*st.lower_bound(mni[0][1]));
		printf("%d ",id.first);
		st.insert(mni[0][1]);
		st.insert(id.second);
		update(mni[0][1]);
		update(id.second);
	}
	printf("\n");
	return 0;
}