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<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;

const int N=200005;
const int inf=1000000000;

int n,a[N],rmq[2][N][20],bin[20],lg[N];
struct data
{
	int l,r,x,y;
	
	bool operator < (const data &p) const
	{
		return a[x]>a[p.x];
	}
};
priority_queue<data> que;

int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

void prepare()
{
	for (int i=1;i<=n;i+=2) rmq[1][i][0]=i;
	for (int i=2;i<=n;i+=2) rmq[0][i][0]=i;
	bin[0]=1;
	for (int i=1;i<=17;i++) bin[i]=bin[i-1]*2;
	for (int i=1;i<=n;i++) lg[i]=log(i)/log(2);
	for (int j=1;j<=lg[n];j++)
		for (int i=1;i+bin[j]-1<=n;i++)
			rmq[0][i][j]=a[rmq[0][i][j-1]]<a[rmq[0][i+bin[j-1]][j-1]]?rmq[0][i][j-1]:rmq[0][i+bin[j-1]][j-1],
			rmq[1][i][j]=a[rmq[1][i][j-1]]<a[rmq[1][i+bin[j-1]][j-1]]?rmq[1][i][j-1]:rmq[1][i+bin[j-1]][j-1];
}

int get_mn(int ty,int l,int r)
{
	int w=lg[r-l+1];
	return a[rmq[ty][l][w]]<a[rmq[ty][r-bin[w]+1][w]]?rmq[ty][l][w]:rmq[ty][r-bin[w]+1][w];
}

data get(int l,int r)
{
	int p=get_mn(l&1,l,r-1),q=get_mn((p&1)^1,p+1,r);
	return (data){l,r,p,q};
}

int main()
{
	n=read();a[0]=inf;
	for (int i=1;i<=n;i++) a[i]=read();
	prepare();
	que.push(get(1,n));
	for (int i=1;i<=n/2;i++)
	{
		data u=que.top();que.pop();
		int l=u.l,r=u.r,x=u.x,y=u.y;
		printf("%d %d ",a[x],a[y]);
		if (l<x-1) que.push(get(l,x-1));
		if (x+1<y-1) que.push(get(x+1,y-1));
		if (y+1<r) que.push(get(y+1,r));
	}
	return 0;
}