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>
#define rep(i,x,y) for (int i=(x); i<=(y); i++)
#define ll long long
#define ld long double
#define inf 1000000000
using namespace std;
ll read(){
	char ch=getchar(); ll x=0; int op=1;
	for (; !isdigit(ch); ch=getchar()) if (ch=='-') op=-1;
	for (; isdigit(ch); ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
	return x*op;
}
#define N 200005
#define lc (o<<1)
#define rc (o<<1|1)
int n,a[N],tr[2][N<<1];
int Min(int x,int y){ return a[x]<a[y]?x:y; }
void up(int typ,int o){ tr[typ][o]=Min(tr[typ][lc],tr[typ][rc]); }
void build(int typ,int o,int l,int r){
	if (l==r){ tr[typ][o]=2*l-typ; return; }
	int mid=l+r>>1;
	build(typ,lc,l,mid); build(typ,rc,mid+1,r);
	up(typ,o);
}
int qry(int typ,int o,int l,int r,int x,int y){
	if (x<=l && r<=y) return tr[typ][o];
	int mid=l+r>>1,ret=0;
	if (x<=mid) ret=Min(ret,qry(typ,lc,l,mid,x,y));
	if (y>mid) ret=Min(ret,qry(typ,rc,mid+1,r,x,y));
	return ret;
}
struct node{
	int l,r,x,y,tg; node(){}
	node(int l_,int r_,int tg_){
		l=l_,r=r_,tg=tg_;
		if (l+1==r) x=l,y=r;
		else{
			if (!tg) x=qry(tg^1,1,1,n/2,(l+1)/2,r/2),y=qry(tg,1,1,n/2,(x+1)/2,r/2);
			else x=qry(tg^1,1,1,n/2,(l+1)/2,r/2),y=qry(tg,1,1,n/2,(x+2)/2,(r+1)/2);
		}
	}
	bool operator < (const node &t) const{ return a[x]>a[t.x]; }
};
priority_queue<node> q;
void ins(int x,int y,int tg){ if (x<y) q.push(node(x,y,tg)); }
int main(){
	n=read();
	rep (i,1,n) a[i]=read(); a[0]=inf;
	build(1,1,1,n/2); build(0,1,1,n/2);
	q.push(node(1,n,0));
	rep (step,1,n/2){
		node tmp=q.top(); q.pop();
		printf("%d %d ",a[tmp.x],a[tmp.y]);
		ins(tmp.l,tmp.x-1,tmp.tg);
		ins(tmp.x+1,tmp.y-1,tmp.tg^1);
		ins(tmp.y+1,tmp.r,tmp.tg);
	}
	return 0;
}