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 <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define N 200005
using namespace std;
struct P{
	int x,y;
}b[N];
struct edge{
	int k,next;
}e[N<<1];
int mn[2][N<<2],n,a[N],tot,home[N],cnt=-1;
void add(int x,int y){
	if(!x||!y) return;
	cnt++;
	e[cnt].k=y;
	e[cnt].next=home[x];
	home[x]=cnt;
}
void build(int k,int l,int r){
	if(l==r){
		mn[l&1][k]=l;
		return;
	}
	int mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	for(int i=0;i<2;i++){
		if(a[mn[i][k<<1]]>a[mn[i][k<<1|1]]) mn[i][k]=mn[i][k<<1|1];
		else mn[i][k]=mn[i][k<<1];
	}
}
int query(int k,int l,int r,int L,int R,int op){
	if(L<=l&&R>=r) return mn[op][k];
	int mid=l+r>>1,ans=0;
	if(L<=mid) ans=query(k<<1,l,mid,L,R,op);
	if(R>mid){
		int t=query(k<<1|1,mid+1,r,L,R,op);
		ans=a[ans]<a[t]?ans:t;
	}
	return ans;
}
int solve(int l,int r){
	if(l>r) return 0;
	int x=query(1,1,n,l,r,l&1);
	int y=query(1,1,n,x+1,r,!(x&1));
	int g=tot+1;
	b[++tot].x=a[x];b[tot].y=a[y];
	add(g,solve(l,x-1));
	add(g,solve(x+1,y-1));
	add(g,solve(y+1,r));
	return g;
}
int id[N];
priority_queue<int,vector<int>,greater<int> >q;
int main(){
	memset(home,-1,sizeof(home));
	scanf("%d",&n);
	a[0]=1e9;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	build(1,1,n);
	int rt=solve(1,n);
	for(int  i=1;i<=tot;i++) id[b[i].x]=i;
	q.push(b[rt].x);
	while(!q.empty()){
		int k=id[q.top()];q.pop();
		printf("%d %d ",b[k].x,b[k].y);
		for(int i=home[k];~i;i=e[i].next) q.push(b[e[i].k].x);
	}
	return 0;
}