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<queue>
using namespace std;
const int N=2e5+5,LG=20;
int n,i,j,k,a[N],lg[N],mn[N][LG];
int read(){
	char c=getchar();int k=0;for (;c<48||c>57;c=getchar());
	for (;c>47&&c<58;c=getchar()) k=(k<<3)+(k<<1)+c-48;return k;
}
void write(int x){if (x>9) write(x/10);putchar(x%10+48);}
int Min(int x,int y){return a[x]<a[y]?x:y;}
int ask(int l,int r){
	int v=lg[(r-l)/2+1];
	return Min(mn[l][v],mn[r-(1<<v)*2+2][v]);
}
struct heap{int l,r,x;};
bool operator < (heap A,heap B){return a[A.x]>a[B.x];}
priority_queue<heap> q;
void ins(int l,int r){
	if (l>r) return;
	q.push((heap){l,r,ask(l,r-1)});
}
int main(){
	for (n=read(),lg[0]=-1,i=1;i<=n;i++)
		a[i]=read(),mn[i][0]=i,lg[i]=lg[i>>1]+1;
	for (j=1,k=2;2*k-1<=n;j++,k<<=1)
		for (i=1;i+2*k-2<=n;i++)
			mn[i][j]=Min(mn[i][j-1],mn[i+k][j-1]);
	ins(1,n);
	while (!q.empty()){
		int l=q.top().l,r=q.top().r;
		int x=q.top().x,y=ask(x+1,r);q.pop();
		write(a[x]);putchar(' ');write(a[y]);putchar(' ');
		ins(l,x-1);ins(x+1,y-1);ins(y+1,r);
	}
}