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<algorithm>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<set>
#define rep(i,x,y) for(int i=x; i<=y; ++i)

using namespace std;
const int N=200005;
int n,a[N],bin[N],pos[N],st[2][20][N];
struct data
{
	int l,r,c;

	bool operator < (const data &t) const
	{
		return c<t.c;
	}
};
set <data> t;

int getint()
{
	char ch;
	while(!isdigit(ch=getchar()));
	int x=ch-48;
	while(isdigit(ch=getchar())) x=x*10+ch-48;
	return x;
}

int query(int l,int r)
{
	int len=bin[r-l+1];
	return min(st[l&1][len][l],st[l&1][len][r-(1<<len)+1]);
}

int main()
{
	n=getint();
	rep(i,1,n) a[i]=getint(),pos[a[i]]=i;
	rep(i,1,n) st[i&1][0][i]=a[i],st[!(i&1)][0][i]=n+1;
	rep(i,2,n) bin[i]=bin[i>>1]+1;
	rep(tp,0,1) rep(i,1,bin[n]) rep(j,1,n-(1<<i)+1) st[tp][i][j]=min(st[tp][i-1][j],st[tp][i-1][j+(1<<i-1)]);
	t.insert((data){1,n,query(1,n)});
	while(!t.empty())
	{
		data p=*t.begin();
		int x=pos[query(p.l,p.r)];
		int y=pos[query(x+1,p.r)];
		printf("%d %d ",a[x],a[y]);
		t.erase(p);
		if(p.l<x-1) t.insert((data){p.l,x-1,query(p.l,x-1)});
		if(x+1<y-1) t.insert((data){x+1,y-1,query(x+1,y-1)});
		if(y+1<p.r) t.insert((data){y+1,p.r,query(y+1,p.r)});
	}
	puts("");
	return 0;
}