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>
const int N=2e5+7;
int n,mx,a[N],t[533333][2];
int min(int a,int b){return a<b?a:b;}
struct itv{
	int l,r;
	int mv,mw;
	bool operator<(const itv&w)const{return mv>w.mv;}
	void init();
	void cal();
};
std::priority_queue<itv>q;
void cal(int l,int r){
	if(l>r)return;
	itv i=(itv){l,r};
	i.init();
	q.push(i);
}
void up(int&w,int l,int r){
	w=a[l]<a[r]?l:r;
}
void itv::init(){
	mw=0;
	for(int L=l+mx-1,R=r+mx+1,d=l&1;R-L>1;L>>=1,R>>=1){
		if(~L&1)up(mw,mw,t[L+1][d]);
		if(R&1)up(mw,mw,t[R-1][d]);
	}
	mv=a[mw];
}
void itv::cal(){
	int p=0;
	for(int L=mw+mx,R=r+mx+1,d=r&1;R-L>1;L>>=1,R>>=1){
		if(~L&1)up(p,p,t[L+1][d]);
		if(R&1)up(p,p,t[R-1][d]);
	}
	::cal(l,mw-1);
	::cal(mw+1,p-1);
	::cal(p+1,r);
	printf("%d %d ",mv,a[p]);
}
int main(){
	scanf("%d",&n);
	for(mx=1;mx<n+5;mx<<=1);
	a[0]=0x3f3f3f3f;
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
		t[mx+i][i&1]=i;
	}
	for(int i=mx-1;i;--i){
		up(t[i][0],t[i<<1][0],t[i<<1^1][0]);
		up(t[i][1],t[i<<1][1],t[i<<1^1][1]);
	}
	cal(1,n);
	while(q.size()){
		itv i=q.top();q.pop();
		i.cal();
	}
	return 0;
}