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;
#define N 210000
int n,cnt;
int a[N],tar[N],ans[N];
vector<int>vec[N];
priority_queue<int,vector<int>,greater<int> >que;
struct Seg_tree
{
	#define ls l,mid,now<<1
	#define rs mid+1,r,now<<1|1
	int v[N];
	int mn[N<<1],pos[N<<1];
	void pushup(int now)
	{
		mn[now]=min(mn[now<<1],mn[now<<1|1]);
		pos[now]=mn[now<<1]<mn[now<<1|1] ? pos[now<<1] : pos[now<<1|1];
	}
	void build(int l,int r,int now)
	{
		if(l==r)
		{
			mn[now]=v[l];pos[now]=l;
			return;
		}
		int mid=(l+r)>>1;
		build(ls);build(rs);
		pushup(now);
	}
	void upd(int &x,int y)
	{x = (!x)||(v[x]>v[y]) ? y : x;}
	int query(int l,int r,int now,int lq,int rq)
	{
		if(lq<=l&&r<=rq)
			return pos[now];
		int mid=(l+r)>>1,ret=0;
		if(mid>=lq)upd(ret,query(ls,lq,rq));
		if(mid<rq) upd(ret,query(rs,lq,rq));
		return ret;
	}
	int query(int l,int r)
	{return query(1,n>>1,1,l,r);}
}tr[2];
int solve(int l,int r)
{
	if(l>r)return 0;
	int t;
	int t1=tr[l&1].query((l+1)>>1,r>>1);t1=(t1<<1)-(l&1);
	int t2=tr[~l&1].query((t1+2)>>1,(r+1)>>1);t2=(t2<<1)-(~l&1);
	tar[a[t1]]=a[t2];
	if(t=solve(l,t1-1))vec[a[t1]].push_back(t);
	if(t=solve(t1+1,t2-1))vec[a[t1]].push_back(t);
	if(t=solve(t2+1,r))vec[a[t1]].push_back(t);
	return a[t1];
}
int main()
{
	//freopen("tt.in","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		tr[i&1].v[(i+1)>>1]=a[i];
	}
	tr[0].build(1,n>>1,1);
	tr[1].build(1,n>>1,1);
	int t=solve(1,n);
	que.push(t);
	while(!que.empty())
	{
		int t=que.top();que.pop();
		for(int i=0;i<vec[t].size();i++)
			que.push(vec[t][i]);
		ans[++cnt]=t;ans[++cnt]=tar[t];
	}
	for(int i=1;i<=n;i++)
		printf("%d ",ans[i]);
	return 0;
}