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<cstdio>
#include<algorithm>
#include<queue>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int maxn=200000+10,inf=1000000000;
int ans[maxn],tree[maxn*4][2],f[maxn];
int i,j,k,l,r,s,t,n,m,tot,top;
struct dong{
	int l,r,u,v;
	friend bool operator <(dong a,dong b){
		return f[a.u]>f[b.u];
	}
} zlt;
priority_queue<dong> heap;
void update(int p){
	int i,j,k;
	fo(i,0,1){
		j=tree[p*2][i];k=tree[p*2+1][i];
		if (f[j]<f[k]) tree[p][i]=j;else tree[p][i]=k;
		//tree[p][i]=min(tree[p*2][i],tree[p*2+1][i]);
	}
}
void build(int p,int l,int r){
	if (l==r){
		tree[p][l%2]=l;
		return;
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);build(p*2+1,mid+1,r);
	update(p);
}
int query(int p,int l,int r,int a,int b,int c){
	if (l==a&&r==b) return tree[p][c];
	int mid=(l+r)/2;
	if (b<=mid) return query(p*2,l,mid,a,b,c);
	else if (a>mid) return query(p*2+1,mid+1,r,a,b,c);
	else{
		int j=query(p*2,l,mid,a,mid,c),k=query(p*2+1,mid+1,r,mid+1,b,c);
		if (f[j]<f[k]) return j;else return k;
	}
}
void ins(int l,int r){
	int j,k;
	j=query(1,1,n,l,r,l%2);
	k=query(1,1,n,j+1,r,r%2);
	zlt.l=l;zlt.r=r;
	zlt.u=j;zlt.v=k;
	heap.push(zlt);
}
int main(){
	scanf("%d",&n);
	f[0]=inf;
	fo(i,1,n) scanf("%d",&f[i]);
	build(1,1,n);
	ins(1,n);
	while (!heap.empty()){
		zlt=heap.top();
		heap.pop();
		l=zlt.l;r=zlt.r;
		j=zlt.u;k=zlt.v;
		ans[++tot]=f[j];ans[++tot]=f[k];
		if (j!=l) ins(l,j-1);
		if (j+1!=k) ins(j+1,k-1);
		if (k!=r) ins(k+1,r);
	}
	fo(i,1,n) printf("%d ",ans[i]);
}