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>
#define pb push_back
#define fi first
#define se second

using namespace std;
typedef pair<int,int> pi;

const int N=100005,M=20;

int n,lg2[N];
struct ST_list{
	int ST[M][N],va[N];
	int Min(int x,int y){return va[x]<va[y]?x:y;}
	void build(){
		for(int i=1;i<=n;i++)ST[0][i]=i;
		for(int l=2,i=1;l<=n;l<<=1,i++)for(int j=1;j<=n-l+1;j++)
			ST[i][j]=min(ST[i-1][j],ST[i-1][j+(l>>1)]);
	}
	int min(int l,int r){
		int d=lg2[r-l+1];
		return Min(ST[d][l],ST[d][r-(1<<d)+1]);
	}
}A,B;

int m;pi id[N];
vector<int>e[N];

int solve(ST_list*a,ST_list*b,int l,int r,bool k){
	int x=a->min(l-k,r-k),y=b->min(x+k,r);
	int p=++m;id[p]={a->va[x],b->va[y]};
	if(l<=x-!k)e[p].pb(solve(a,b,l,x-!k,k));
	if(x+1<=y-k)e[p].pb(solve(b,a,x+1,y-k,k^1));
	if(y+1<=r)e[p].pb(solve(a,b,y+1,r,k));
	return p;
}

typedef pair<pi,int> ppi;
priority_queue<ppi,vector<ppi>,greater<ppi>> que;

int main(){
	scanf("%d",&n);n>>=1;
	for(int i=1;i<=n;i++)scanf("%d%d",&A.va[i],&B.va[i]);
	A.build();B.build();
	for(int i=2;i<=n;i++)lg2[i]=lg2[i-1]+!(i&(i-1));
	solve(&A,&B,1,n,0);
	que.push({id[1],1});
	while(que.size()){
		auto t=que.top();que.pop();
		printf("%d %d ",t.fi.fi,t.fi.se);
		for(int v:e[t.se])que.push({id[v],v});
	}
	return 0;
}