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
#include<bits/stdc++.h>
using namespace std;
int n,p[200005],pos[200005],fi,se;
int st[200005][20][2],lg[200005];
struct node{
	int x,y,l,r;
}a;
struct cmp{bool operator()(node u,node v){return u.x>v.x;}};
priority_queue<node,vector<node>,cmp> q;

int read(){
	int x=0;char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}

void print(int x){
	if(x>=10) print(x/10);
	putchar(x%10+'0');
}

int query(int x,int y){
	int len=y-x+1;len=lg[len];
	return min(st[x][len][x%2],st[y-(1<<len)+1][len][x%2]);
}

int main(){
	n=read();
	for(int i=1;i<=n;i++){
		p[i]=read(),pos[p[i]]=i;
		st[i][0][i%2]=p[i],st[i][0][(i%2)^1]=n+1;
	}
	lg[1]=0;for(int i=2;i<=n;i++) lg[i]=lg[i/2]+1;
	for(int j=1;j<=19;j++){
		for(int i=1;i<=n-(1<<j)+1;i++){
			st[i][j][0]=min(st[i][j-1][0],st[i+(1<<(j-1))][j-1][0]);
			st[i][j][1]=min(st[i][j-1][1],st[i+(1<<(j-1))][j-1][1]);
		}
	}
	fi=query(1,n);se=query(pos[fi]+1,n);
	q.push((node){fi,se,1,n});
	while(!q.empty()){
		a=q.top();q.pop();
		print(a.x),putchar(' '),print(a.y),putchar(' ');
		if(a.l<pos[a.x]-1){
			fi=query(a.l,pos[a.x]-1),se=query(pos[fi]+1,pos[a.x]-1);
			q.push((node){fi,se,a.l,pos[a.x]-1});
		}
		if(pos[a.x]+1<pos[a.y]-1){
			fi=query(pos[a.x]+1,pos[a.y]-1),se=query(pos[fi]+1,pos[a.y]-1);
			q.push((node){fi,se,pos[a.x]+1,pos[a.y]-1});
		}
		if(pos[a.y]+1<a.r){
			fi=query(pos[a.y]+1,a.r),se=query(pos[fi]+1,a.r);
			q.push((node){fi,se,pos[a.y]+1,a.r});
		}
	}
	puts("");

	return 0;
}