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 <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<queue>
#define sqr(x) (x)*(x)
#define mk(x,y,z) make_pair(x,make_pair(y,z))
using namespace std;
int n,m,i,j,mi[1000005][2],num[1000005],re[1000005],x,y,l,r;
priority_queue<pair<int,pair<int,int>/**/>,vector<pair<int,pair<int,int>/**/>/**/>,greater<pair<int,pair<int,int>/**/>/**/>/**/> pq;
void build(int id,int l,int r)
{
	if (l==r)
	{
		mi[id][l&1]=num[l];
		mi[id][(l&1)^1]=n+1;
		return;
	}
	build(id*2,l,(l+r)/2);
	build(id*2+1,(l+r)/2+1,r);
	mi[id][0]=min(mi[id*2][0],mi[id*2+1][0]);
	mi[id][1]=min(mi[id*2][1],mi[id*2+1][1]);
}
int query(int id,int l,int r,int ql,int qr,int t)
{
	if (ql<=l&&r<=qr) return mi[id][t];
	int ans=n+1;
	if (ql<=(l+r)/2) ans=min(ans,query(id*2,l,(l+r)/2,ql,qr,t));
	if (qr>(l+r)/2) ans=min(ans,query(id*2+1,(l+r)/2+1,r,ql,qr,t));
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	cin>>n;
	for (i=1;i<=n;i++)
	{
		cin>>num[i];
		re[num[i]]=i;
	}
	build(1,1,n);
	pq.push(mk(query(1,1,n,1,n,1),1,n));
	for (i=1;i<=n/2;i++)
	{
		x=pq.top().first;
		y=query(1,1,n,re[x]+1,pq.top().second.second,(re[x]+1)&1);
		cout<<x<<' '<<y<<' ';
		x=re[x];
		y=re[y];
		l=pq.top().second.first;
		r=pq.top().second.second;
		pq.pop();
		if (l<x-1) 
		{
			pq.push(mk(query(1,1,n,l,x-1,l&1),l,x-1));
		}
		if (x+1<y-1)
		{
			pq.push(mk(query(1,1,n,x+1,y-1,(x+1)&1),x+1,y-1));
		}
		if (y+1<r)
		{
			pq.push(mk(query(1,1,n,y+1,r,(y+1)&1),y+1,r));
		}
	}
	return 0;
}