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>
int N,p[200010],st[2][18][100010],log[100010];
int minp(int a,int b){return p[a]<p[b]?a:b;}
int qry(int t,int l,int r){
	int k=log[r-l];
	return minp(st[t][k][l],st[t][k][r-(1<<k)]);
}
struct item{
	int l,r,pl,pr;
	bool operator<(const item&it)const{
		return p[pl]>p[it.pl];
	}
};
item get(int l,int r){
	int pl=qry(l%2,l/2,r/2),pr=qry((l+1)%2,(pl+1)/2,(r+1)/2);
	return(item){l,r,pl,pr};
}
std::priority_queue<item>Q;
int main(){
	scanf("%d",&N);
	for(int i=0;i<N;i++)scanf("%d",p+i),st[i%2][0][i/2]=i;
	N/=2;
	for(int i=2;i<=N;i++)log[i]=log[i/2]+1;
	for(int t=0;t<2;t++)
		for(int k=1;k<=log[N];k++)
			for(int i=0;i+(1<<k)<=N;i++)
				st[t][k][i]=minp(st[t][k-1][i],st[t][k-1][i+(1<<k-1)]);
	Q.push(get(0,N*2));
	while(!Q.empty()){
		item it=Q.top();Q.pop();
		printf("%d %d ",p[it.pl],p[it.pr]);
		if(it.l<it.pl)Q.push(get(it.l,it.pl));
		if(it.pl+1<it.pr)Q.push(get(it.pl+1,it.pr));
		if(it.pr+1<it.r)Q.push(get(it.pr+1,it.r));
	}
}