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<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
priority_queue<int,vector<int>,greater<int> >Heap;
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
int v[200005],first[200005],nex[200005],e;
void AddEdge(int U,int V){
	v[++e]=V;
	nex[e]=first[U];
	first[U]=e;
}
int a[200005],cnt,ma[200005],pai[200005];
int minv[2][100005<<4],n,pos[200005];
void update(int o,int p,int v,int rt,int l,int r)
{
    if(l==r)
      {
        minv[o][rt]+=v;
        return;
      }
    int m=(l+r>>1);
    if(p<=m) update(o,p,v,lson);
    else update(o,p,v,rson);
    minv[o][rt]=min(minv[o][rt<<1],minv[o][rt<<1|1]);
}
int query(int o,int ql,int qr,int rt,int l,int r)
{
    if(ql<=l&&r<=qr) return minv[o][rt];
    int m=(l+r>>1);
    int res=2147483647;
    if(ql<=m) res=min(res,query(o,ql,qr,lson));
    if(m<qr) res=min(res,query(o,ql,qr,rson));
    return res;
}
void work(int l,int r,int f){
	if(l>=r){
		return;
	}
	int L=pos[query(l&1,ma[l],(l%2 == r%2) ? ma[r] : ma[r-1],1,1,n/2)];
	int R=pos[query((L+1)&1,ma[L+1],((L+1)%2 == r%2) ? ma[r] : ma[r-1],1,1,n/2)];
	pai[a[L]]=a[R];
	AddEdge(a[f],a[L]);
	work(l,L-1,f);
	work(L+1,R-1,L);
	work(R+1,r,f);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		pos[a[i]]=i;
		update(i&1,i/2+(i&1),a[i],1,1,n/2);
		ma[i]=i/2+(i&1);
	}
	if(n==2){
		printf("%d %d\n",a[1],a[2]);
		return 0;
	}
	work(1,n,0);
	for(int i=first[0];i;i=nex[i]){
		Heap.push(v[i]);
	}
	while(!Heap.empty()){
		int U=Heap.top(); Heap.pop();
		cnt+=2;
		printf("%d %d%c",U,pai[U],cnt==n ? '\n' : ' ');
		for(int i=first[U];i;i=nex[i]){
			Heap.push(v[i]);
		}
	}
	return 0;
}