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>
#define ls  (n<<1)
#define rs  ((n<<1)|1)
using namespace std;

struct node{int l,r,x,y;};
int n,a[200010],b[200010],t[2][400010];
set <node> S;

bool operator < (node x,node y){return a[x.x]<a[y.x];}

void build(int op,int n,int l,int r)
{
	if (l==r)  t[op][n]=a[2*l-op];
	else
		{
			int mid=(l+r)>>1;
			build(op,ls,l,mid),build(op,rs,mid+1,r);
			t[op][n]=min(t[op][ls],t[op][rs]);
		}
}

int ask(int op,int n,int l,int r,int L,int R)
{
	if ((L<=l)&&(r<=R))  return t[op][n];
	else
		{
			int mid=(l+r)>>1;
			if (mid>=R)  return ask(op,ls,l,mid,L,R);
			if (L>mid)  return ask(op,rs,mid+1,r,L,R);
			return min(ask(op,ls,l,mid,L,R),ask(op,rs,mid+1,r,L,R));
		}
}

void doit(int l,int r)
{
	int x,y;
	if (l&1)
		{
			x=b[ask(1,1,1,n/2,l/2+1,r/2)],y=b[ask(0,1,1,n/2,x/2+1,r/2)];
		}else
		{
			x=b[ask(0,1,1,n/2,l/2,r/2)],y=b[ask(1,1,1,n/2,x/2+1,r/2+1)];
		}
	S.insert((node){l,r,x,y});
}

void work()
{
	scanf("%d",&n);
	for (int i=1; i<=n; i++)  scanf("%d",&a[i]),b[a[i]]=i;
	build(0,1,1,n/2),build(1,1,1,n/2);
	int x=b[ask(1,1,1,n/2,1,n/2)],y=b[ask(0,1,1,n/2,x/2+1,n/2)];
	S.insert((node){1,n,x,y});
	for (node p; S.size(); )
		{
			p=*S.begin(),S.erase(S.begin());
			printf("%d %d ",a[p.x],a[p.y]);
			if (p.l!=p.x)  doit(p.l,p.x-1);
			if (p.x+1!=p.y)  doit(p.x+1,p.y-1);
			if (p.y!=p.r)  doit(p.y+1,p.r);
		}
}

int main()
{
	work();
	return 0;
}