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<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define N 1000100
#define inf 100000000
#define ls (rt<<1)
#define rs (rt<<1|1)
#define fi first
#define se second
struct node{int a,b,id;}p[N];
typedef pair<int,int> pa;
bool operator < (node x,node y){if (x.a==y.a) return x.b>y.b;return x.a>y.a;}
priority_queue<node> que;
int n,i,a[N],cnt,pos[N];pa minn[N<<3];
vector<int> e[N],ans;
void cmp(pa &x,pa y) {x.fi=min(x.fi,y.fi),x.se=min(x.se,y.se);}
void build(int rt,int l,int r)
{	
	minn[rt].fi=inf;minn[rt].se=inf;
	if (l==r){if (l&1) minn[rt].fi=a[l];else minn[rt].se=a[l];return ;}
	int mid=(l+r)/2;build(ls,l,mid);build(rs,mid+1,r);
	cmp(minn[rt],minn[ls]),cmp(minn[rt],minn[rs]);
}
pa query(int rt,int l,int r,int x,int y)
{
	if (x<=l&&r<=y) return minn[rt];
	int mid=(l+r)/2;
	pa ret=make_pair(inf,inf);
	if(x<=mid) cmp(ret,query(ls,l,mid,x,y));
	if (y>=mid+1) cmp(ret,query(rs,mid+1,r,x,y));
	return ret;
}
int solve(int l,int r)
{
	int tmpa,tmpb,posa,posb;
	if (l&1)
	{
		tmpa=query(1,1,n,l,r).fi,posa=pos[tmpa];
		tmpb=query(1,1,n,posa+1,r).se,posb=pos[tmpb];
	}else
	{
		tmpa=query(1,1,n,l,r).se,posa=pos[tmpa];
		tmpb=query(1,1,n,posa+1,r).fi,posb=pos[tmpb];
	}
	p[++cnt].a=tmpa,p[cnt].b=tmpb,p[cnt].id=cnt;
	int cntt=cnt;
	if (posa!=l)  e[cntt].push_back(solve(l,posa-1));
	if (posa+1!=posb)  e[cntt].push_back(solve(posa+1,posb-1));
	if (posb!=r)  e[cntt].push_back(solve(posb+1,r));
	return cntt;
}
int main()
{
	scanf("%d",&n);
	for (i=1;i<=n;i++)scanf("%d",&a[i]),pos[a[i]]=i;
	build(1,1,n);
	solve(1,n);
	que.push(p[1]);
	while (!que.empty())
	{
		int x=que.top().id;que.pop();
		printf("%d %d ",p[x].a,p[x].b);
		for (i=0;i<(int)e[x].size();i++)que.push(p[e[x][i]]);
	}
}