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<iostream>
#include<queue>
using namespace std;
const int N=200010;
struct tree{
	int l,r,ji,ou;
}tr[4*N];
int id[N];
int n,a[N];
bool se=0;
struct node{
	friend bool operator < (node a,node b){return a.x>b.x;}
	int x,y,l,r;
}q,pu;
priority_queue<node> ans;
const int inf=1e9;
void update(int i){tr[i].ji=min(tr[i<<1].ji,tr[i<<1|1].ji);tr[i].ou=min(tr[i<<1].ou,tr[i<<1|1].ou);}
void build(int i,int l,int r)
{
	tr[i].l=l;
	tr[i].r=r;
	if (l==r){if (l&1) tr[i].ji=a[l],tr[i].ou=inf;else tr[i].ji=inf,tr[i].ou=a[l];return;}
	int mid=l+r>>1;build(i<<1,l,mid);build(i<<1|1,mid+1,r);update(i);	
}
int query(int i,int l,int r,int p)
{
	int L=tr[i].l;int R=tr[i].r;
	if (L>r||l>R) return inf;
	if (l<=L && R<=r){if (p) return tr[i].ji; else return tr[i].ou;}
	int ans=inf;ans=min(ans,query(i<<1,l,r,p));ans=min(ans,query(i<<1|1,l,r,p));return ans;
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]),id[a[i]]=i;
	build(1,1,n);
	int x=query(1,1,n,1);int y=query(1,id[x]+1,n,0);
	q.l=1;q.r=n;q.x=x;q.y=y;ans.push(q);
	for (int i=2;i<=n/2;i++)
	{
		q=ans.top();ans.pop();int ix=id[q.x];int iy=id[q.y];
		if (q.l<ix){se=q.l&1;int x=query(1,q.l,ix-1,se);int y=query(1,id[x],ix-1,se^1);pu.l=q.l;pu.r=ix-1;pu.x=x;pu.y=y;ans.push(pu); }
		if (ix+1<iy){se=(ix+1)&1;int x=query(1,ix+1,iy-1,se);int y=query(1,id[x]+1,iy-1,se^1);pu.l=ix+1;pu.r=iy-1;pu.x=x;pu.y=y;ans.push(pu);}
		if (iy<q.r){se=(iy+1)&1;int x=query(1,iy+1,q.r,se);int y=query(1,id[x]+1,q.r,se^1);pu.l=iy+1;pu.r=q.r;pu.x=x;pu.y=y;ans.push(pu);}
		printf("%d %d ",q.x,q.y);
	}
	while (!ans.empty()){pu=ans.top();ans.pop();printf("%d %d ",pu.x,pu.y);}
}