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<iostream>
#include<cstdio>
#include<queue>
#define pii pair<int,int>
#define piii pair<pii,int>
using namespace std;
int cnt,n,root,sz,a[201010];
int mi[804040][2],fir[201010],nxt[402020],to[402020];
pii num[201010];
priority_queue<piii,vector<piii>,greater<piii> > q;
void add(int x,int y)
{
	nxt[++cnt]=fir[x];fir[x]=cnt;to[cnt]=y;
}
int mmin(int x,int y){ return a[x]<a[y]?x:y;}
void build(int nd,int l,int r)
{
	if(l==r)
	{
		mi[nd][l&1]=l;
		mi[nd][l&1^1]=0;
		return ;
	}
	int mid=(l+r)/2;
	build(nd<<1,l,mid);
	build(nd<<1|1,mid+1,r);
	mi[nd][0]=mmin(mi[nd<<1][0],mi[nd<<1|1][0]);
	mi[nd][1]=mmin(mi[nd<<1][1],mi[nd<<1|1][1]);
}
int query(int nd,int l,int r,int ql,int qr,int d)
{
	if(l>qr||r<ql) return 0;
	if(l>=ql&&r<=qr) return mi[nd][d];
	int mid=(l+r)/2;
	return mmin(query(nd<<1,l,mid,ql,qr,d),query(nd<<1|1,mid+1,r,ql,qr,d));
}
void solve(int &k,int l,int r)
{
	if(l>=r) return ;
	int d=(l&1);
	int k1=query(1,1,n,l,r,d),k2=query(1,1,n,k1+1,r,d^1),ch=0;
//	cout<<l<<" "<<r<<" "<<k1<<" "<<k2<<endl;
	num[k=++sz]=make_pair(a[k1],a[k2]);
	solve(ch,l,k1-1);if(ch) add(k,ch),ch=0;
	solve(ch,k1+1,k2-1);if(ch) add(k,ch),ch=0;
	solve(ch,k2+1,r);if(ch) add(k,ch),ch=0;
}
void print()
{
	q.push(make_pair(num[root],root));
	while(!q.empty())
	{
		int x=q.top().second;q.pop();
		printf("%d %d ",num[x].first,num[x].second);
		for(int i=fir[x];i;i=nxt[i])
		q.push(make_pair(num[to[i]],to[i]));
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);a[0]=0x3f3f3f3f;
	build(1,1,n);
	solve(root,1,n);
	print();
	return 0;
}