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<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const int N=2e5+11,INF=~0u>>2;
struct node{
	int x,l,r;
	bool operator<(const node&b)const{return x>b.x;}
};
priority_queue<node> Q;
int n,d[2][N][25],a[2][N],pos[N];
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return f*x;
}
void RMQ_init(int f){
	for(int i=1;i<=n;++i) d[f][i][0]=a[f][i];
	for(int j=1;(1<<j)<=n;++j) 
	   for(int i=1;(i+(1<<j)-1)<=n;++i)
	      d[f][i][j]=min(d[f][i][j-1],d[f][i+(1<<(j-1))][j-1]);
}
int RMQ(int l,int r,int f){
	int k=0;
	while((1<<(k+1))<=r-l+1) k++;
	return min(d[f][l][k],d[f][r-(1<<k)+1][k]);
}
int main(){
//	freopen("ex.in","r",stdin);
	n=read();
	for(int i=1;i<=n;++i){
		int tmp=read();
		a[i&1][i]=tmp;
		a[(i&1)^1][i]=INF;
		pos[tmp]=i;
		
	}
	RMQ_init(0);RMQ_init(1);
	Q.push((node){RMQ(1,n,1),1,n});
	while(!Q.empty()){
		node x=Q.top();Q.pop();
		int v1=x.x,v2=RMQ(pos[x.x]+1,x.r,(pos[x.x]&1)^1);
		printf("%d %d ",v1,v2);
		v1=pos[v1];v2=pos[v2];
		if(x.l!=v1) Q.push((node){RMQ(x.l,v1-1,x.l&1),x.l,v1-1});
		if(v1+1!=v2) Q.push((node){RMQ(v1+1,v2-1,(v1+1)&1),v1+1,v2-1});
		if(v2!=x.r) Q.push((node){RMQ(v2+1,x.r,(v2+1)&1),v2+1,x.r});
	}
	return 0;
}