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>

using namespace std;

#define N 300000
#define ls (x<<1)
#define rs (x<<1|1)

int n,a[N],seg[N<<2][2],pos[N];
struct node{
	int x,l,r;
	node(int x=0,int l=0,int r=0):x(x),l(l),r(r){}
	bool operator < (const node &w) const{
		return x>w.x;
	}
};
priority_queue<node> pq;

void build(int x,int l,int r){
	if (l==r){seg[x][l&1]=a[l]; seg[x][(l&1)^1]=n+1; return;}
	int mid=(l+r)>>1;
	build(ls,l,mid); build(rs,mid+1,r);
	seg[x][0]=min(seg[ls][0],seg[rs][0]);
	seg[x][1]=min(seg[ls][1],seg[rs][1]);
}

int qry(int x,int l,int r,int L,int R,int k){
	if (l>=L&&r<=R) return seg[x][k];
	int mid=(l+r)>>1,ret=n+1;
	if (L<=mid) ret=min(ret,qry(ls,l,mid,L,R,k));
	if (R>mid) ret=min(ret,qry(rs,mid+1,r,L,R,k));
	return ret;
}

int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;++i){
		scanf("%d",a+i);
		pos[a[i]]=i;
	}
	build(1,1,n);
	pq.push(node(qry(1,1,n,1,n,1),1,n));
	while (!pq.empty()){
		int l=pq.top().l,r=pq.top().r; pq.pop();
		int u=qry(1,1,n,l,r,l&1),v=qry(1,1,n,pos[u]+1,r,r&1);
		printf("%d %d ",u,v);
		u=pos[u]; v=pos[v];
		if (l<u) pq.push(node(qry(1,1,n,l,u-1,l&1),l,u-1));
		if (u+1<v) pq.push(node(qry(1,1,n,u+1,v-1,v&1),u+1,v-1));
		if (v<r) pq.push(node(qry(1,1,n,v+1,r,u&1),v+1,r));
	}
	puts("");
	
	return 0;
}