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 maxn 300100
using namespace std;
typedef pair<int,int> par;
struct data{int l,r,w,x,y;int operator<(const data& d)const{return w>d.w;}};
priority_queue<data>pq;
int n,a[2][maxn>>1];
par s[2][19][maxn>>1];
par qry(int d,int l,int r){
	int len=1,k=0;
	l=(l+1)>>1,r=(r+1)>>1;
	while((len<<1)<r-l+1)len<<=1,k++;
	return min(s[d][k][l],s[d][k][r-(1<<k)+1]);
}
data get(int l,int r){
	par a1=qry(l&1,l,r-1);
	par b1=qry(~l&1,a1.second+1,r);
	data d;
	d.l=l,d.r=r,d.w=a1.first;
	d.x=a1.second,d.y=b1.second;
	return d;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i&1][(i+1)>>1]);
	memset(s,0x3f,sizeof(s));
	for(int d=0;d<2;++d){
		for(int i=1;i<=((n+1)>>1);++i)s[d][0][i]=par(a[d][i],(i<<1)-d);
		for(int i=1;i<19;++i)
			for(int j=1;j<=((n+1)>>1);++j)
				s[d][i][j]=min(s[d][i-1][j],s[d][i-1][j+(1<<i-1)]);
	}
	pq.push(get(1,n));
	while(pq.size()){
		data ret=pq.top();pq.pop();
//		printf("[%d,%d(%d,%d)]",ret.l,ret.r,ret.x,ret.y);
		printf("%d %d ",a[ret.x&1][(ret.x+1)>>1],a[ret.y&1][(ret.y+1)>>1]);
		if(ret.l<=ret.x-1)pq.push(get(ret.l,ret.x-1));
		if(ret.x+1<=ret.y-1)pq.push(get(ret.x+1,ret.y-1));
		if(ret.r>=ret.y+1)pq.push(get(ret.y+1,ret.r));
	}
}