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 N 200009
using namespace std;

int n,a[N],lg[N];
struct node{ int x,y; }f[2][18][N];
bool operator <(node u,node v){ return u.x<v.x; }
struct itv{ int l,r,k; };
bool operator <(itv u,itv v){ return a[u.k]>a[v.k]; }
priority_queue<itv> Q;
int getmin(int x,int y,int z){
	z^=(x&1);
	int k=lg[y-x+1];
	return min(f[z][k][x],f[z][k][y-(1<<k)+1]).y;
}
void ins(int l,int r){
	if (l<r) Q.push((itv){l,r,getmin(l,r,0)});
}
int main(){
	scanf("%d",&n);
	int i,j,k,x,y;
	for (i=1; i<=n; i++){
		scanf("%d",&a[i]);
		f[i&1][0][i]=(node){a[i],i};
		f[i&1^1][0][i]=(node){n+1,i};
	}
	for (i=2; i<=n; i++) lg[i]=lg[i>>1]+1;
	for (i=0; i<2; i++)
		for (j=1; j<=17; j++)
			for (k=1; k<=n; k++){
				f[i][j][k]=f[i][j-1][k];
				if (k+(1<<j-1)<=n) f[i][j][k]=min(f[i][j][k],f[i][j-1][k+(1<<j-1)]);
			}
	ins(1,n);
	itv u;
	while (!Q.empty()){
		u=Q.top(); Q.pop();
		x=u.k; y=getmin(x,u.r,1);
		printf("%d %d ",a[x],a[y]);
		ins(u.l,x-1); ins(x+1,y-1); ins(y+1,u.r);
	}
	return 0;
}