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<bits/stdc++.h>
using namespace std;
int p[200005],q[200005],a[200005],b[200005];
pair<int,int>seg[2][1000005];
struct node
{
	int l,r,mno,mne,t;
}prt[200005];
node dvd(int l,int r,int mno,int mne,int t)
{
	node ans;
	ans.l=l;ans.r=r;ans.mno=mno;ans.mne=mne;ans.t=t;
	return ans;
}
void build(int x,int l,int r)
{
	if(l==r)
	{
		seg[0][x]=make_pair(a[l],l);
		seg[1][x]=make_pair(b[l],l);
		return;
	}
	int md=(l+r)/2;
	build(x*2,l,md);
	build(x*2+1,md+1,r);
	seg[0][x]=min(seg[0][x*2],seg[0][x*2+1]);
	seg[1][x]=min(seg[1][x*2],seg[1][x*2+1]);
}
pair<int,int> qry(int x,int l,int r,int ll,int rr,int t)
{
	if(ll>r||rr<l)return make_pair(1e9+7,-1);
	if(l<=ll&&r>=rr)return seg[t][x];
	int md=(ll+rr)/2;
	return min(qry(x*2,l,r,ll,md,t),qry(x*2+1,l,r,md+1,rr,t));
}
int n,cc;
set<pair<int,int> >s;
void doit(int l,int r,int t)
{
	if(l>r)return;
	int mno,mne;
	if(t==1)
	{
		mno=qry(1,l,r,1,n,0).second;
		mne=qry(1,mno,r,1,n,1).second;
	}
	else
	{
		mno=qry(1,l,r,1,n,1).second;
		mne=qry(1,mno,r,1,n,0).second;
	}
	prt[++cc]=dvd(l,r,mno,mne,t);		
	s.insert(make_pair(p[mno],cc));
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&p[i]);
	for(int i=1;i<=n;i++)a[i]=b[i]=1e9+7;
	for(int i=1;i<=n;i++)if(i&1)a[i]=p[i];else b[i]=p[i];
	build(1,1,n);
	int mno=qry(1,1,n,1,n,0).second;
	int mne=qry(1,mno,n,1,n,1).second;
	cc=1;
	prt[cc]=dvd(1,n,mno,mne,1);
	s.insert(make_pair(p[mno],cc));
	for(int i=1;i<=n;i+=2)
	{
		set<pair<int,int> >::iterator it=s.begin();
		int x=it->second;
		s.erase(it);
		q[i]=p[prt[x].mno];
		q[i+1]=p[prt[x].mne];
		int t=prt[x].t;
		doit(prt[x].l,prt[x].mno-1,t);
		doit(prt[x].mno+1,prt[x].mne-1,t^1);
		doit(prt[x].mne+1,prt[x].r,t);
	}
	for(int i=1;i<=n;i++)printf("%d ",q[i]);
	puts("");
	return 0;
}