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<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef pair<ll,ll> pll;
typedef pair<int,ii> iii;
const int N = 2e5+1,L = 19;
int f[L][N],a[N],pos[N];
priority_queue<iii,vector<iii>,greater<iii>>pq;
int find(int l,int r)
{
	int sz = log2((r-l)/2+1);
	return min(f[sz][l],f[sz][r-((1<<sz)-1)*2]);
}
void add(int l,int r)
{
	if(l<=r)
	{
		int mn = find(l,r-1);
		pq.push(iii(mn,ii(l,r)));
	}
}
int main()
{
	int n,i,j;
	scanf("%d",&n);
	for(i=0;i<n;i++)	
	{
		scanf("%d",&a[i]);
		pos[a[i]] = i;
	}
	for(i=0;i<n;i++)	f[0][i]=a[i];
	for(i=1;i<L;i++)
	{
		for(j=0;j<n;j++)
		{
			f[i][j] = f[i-1][j];
			if(j+(1<<i)<n)	f[i][j]=min(f[i][j],f[i-1][j+(1<<i)]);
		}
	}
	add(0,n-1);
	for(i=0;i<n;i+=2)
	{
		iii p = pq.top();pq.pop();
		int l=p.second.first;
		int r=p.second.second;
		int min1 = find(l,r-1);
		int p1=pos[min1];
		int min2 = find(p1+1,r);
		int p2=pos[min2];
		printf("%d %d ",min1,min2);
		add(l,p1-1);add(p1+1,p2-1);add(p2+1,r);
	}
}
