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(w,x,y,z) make_pair(make_pair(w,x),make_pair(y,z))
using namespace std;
int n,m,i,j,num[200005],pos[200005];
priority_queue<pair<pair<int,int>,pair<int,int> > > pq;
struct seg
{
	struct node
	{
		int l,r,sum[2];
	}tr[800005];
	void pushup(int x)
	{
		tr[x].sum[0]=max(tr[x*2].sum[0],tr[x*2+1].sum[0]);
		tr[x].sum[1]=max(tr[x*2].sum[1],tr[x*2+1].sum[1]);
	}
	void build(int x,int l,int r)
	{
		tr[x].l=l;
		tr[x].r=r;
		memset(tr[x].sum,-22,sizeof(tr[x].sum));
		if (l!=r)
		{
			int mid=(l+r)/2;
			build(x*2,l,mid);
			build(x*2+1,mid+1,r);
			pushup(x);
		}
		else
		{
			tr[x].sum[l&1]=num[l];
		}
	}
	int query(int x,int l,int r,int c)
	{
		if (tr[x].l>r||tr[x].r<l) return -0x16161616;
		if (tr[x].l>=l&&tr[x].r<=r) return tr[x].sum[c];
		return max(query(x*2,l,r,c),query(x*2+1,l,r,c));
	}
}tr;
void insert(int x,int y)
{
	int t=tr.query(1,x,y,x&1);
	pq.push(mk(t,tr.query(1,pos[-t]+1,y,(!(pos[-t]&1))),x,y));
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin>>n; 
	for (i=1;i<=n;i++)
	{
		cin>>num[i];
		pos[num[i]]=i;
		num[i]=-num[i];
	}
	tr.build(1,1,n);
	int t=tr.query(1,1,n,1);
	pq.push(mk(t,tr.query(1,pos[-t]+1,n,(!(pos[-t]&1))),1,n));
	while (!pq.empty())
	{
		int y=-pq.top().first.first;
		int z=-pq.top().first.second;
		int w=pq.top().second.first;
		int x=pq.top().second.second;
		//cerr<<w<<' '<<x<<' '<<y<<' '<<z<<endl;
		pq.pop();
		cout<<y<<' '<<z<<' ';
		y=pos[y];
		z=pos[z];
		if (w<y-1) insert(w,y-1);
		if (z+1<x) insert(z+1,x);
		if (y+1<z-1) insert(y+1,z-1);
	}
	return 0;
}