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<stdio.h>
#include<queue>
const int N=2e5+3,K=18;
int n,fn[2][N][K],a[N],lg[N];
struct node{
	int l,r,p,f;
	bool operator<(const node&b)const{return a[p]>a[b.p];}
};
std::priority_queue<node> q;
inline int Min(int l,int r,int k){
	int t=lg[r-l];
	if(a[fn[k][l][t]]<a[fn[k][r-(1<<t)][t]])
	  return fn[k][l][t];
	return fn[k][r-(1<<t)][t];
}
int main(){
	node u;int b;
	scanf("%d",&n);
	for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
	a[n]=n+1;
	for(int i=0;i<n;i++){
	  scanf("%d",a+i);
	  fn[i&1][i][0]=i;
	  fn[~i&1][i][0]=n;
	}
	for(int k=0;k<2;k++)
	  for(int j=1;j<K;j++)
		for(int i=0;i+(1<<j)<=n;i++)
		  if(a[fn[k][i][j-1]]<a[fn[k][i+(1<<j-1)][j-1]])
			fn[k][i][j]=fn[k][i][j-1];
		  else fn[k][i][j]=fn[k][i+(1<<j-1)][j-1];
	q.push((node){0,n,Min(0,n,0),0});
	for(;!q.empty();){
	  u=q.top(),q.pop();
	  b=Min(u.p+1,u.r,u.f^1);
	  printf("%d %d ",a[u.p],a[b]);
	  if(u.l<u.p)q.push((node){u.l,u.p,Min(u.l,u.p,u.f),u.f});
	  if(u.p+1<b)q.push((node){u.p+1,b,Min(u.p+1,b,u.f^1),u.f^1});
	  if(b+1<u.r)q.push((node){b+1,u.r,Min(b+1,u.r,u.f),u.f});
	}
	return 0;
}