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<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=2e5+5;
int n,p[N],pos[N],b[N];
bool vis[N];
struct data{
	int l,r,x,y;
	inline bool operator<(const data&rhs)const{return x>rhs.x;}
};
priority_queue<data>q;
struct sgt_{
	int d[N<<2];
	void build(int l,int r,int o){
		if(l==r)d[o]=b[l];else{
			const int mid=l+r>>1;
			build(l,mid,o<<1),build(mid+1,r,o<<1|1);
			d[o]=min(d[o<<1],d[o<<1|1]);
		}
	}
	void modify(int l,int r,int o,const int&pos,const int&x){
		if(l==r)d[o]=x;else{
			const int mid=l+r>>1;
			if(pos<=mid)modify(l,mid,o<<1,pos,x);else modify(mid+1,r,o<<1|1,pos,x);
			d[o]=min(d[o<<1],d[o<<1|1]);
		}
	}
	int query(int l,int r,int o,const int&L,const int&R){
		if(L<=l&&r<=R)return d[o];
		const int mid=l+r>>1;
		if(L<=mid&&mid<R)return min(query(l,mid,o<<1,L,R),query(mid+1,r,o<<1|1,L,R));
		if(L<=mid)return query(l,mid,o<<1,L,R);
		return query(mid+1,r,o<<1|1,L,R);
	}
}t[2];
void add(int l,int r){
	if(l>r)return;
	int x=t[l&1].query(1,n,1,l,r),y=t[l&1^1].query(1,n,1,pos[x]+1,r);
	q.push((data){l,r,x,y});
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d",p+i),pos[p[i]]=i;
	memset(b,0x3f,sizeof b);
	for(int i=1;i<=n;i+=2)b[i]=p[i];
	t[1].build(1,n,1);
	memset(b,0x3f,sizeof b);
	for(int i=2;i<=n;i+=2)b[i]=p[i];
	t[0].build(1,n,1);
	add(1,n);
	while(!q.empty()){
		data u=q.top();q.pop();
		printf("%d %d ",u.x,u.y);
		add(u.l,pos[u.x]-1),add(pos[u.x]+1,pos[u.y]-1),add(pos[u.y]+1,u.r);
	}
	return 0;
}