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<bits/stdc++.h>
#define PAIR pair<int,int>
#define L(__) (__ << 1)
#define R(__) (L(__)|1)
#define oo (1<<30)
#define N 200005
using namespace std;
vector<int> G[N];
set<PAIR> S;
PAIR C[N];
int n,m,a[N],A[4*N],B[4*N];
int minself(int x,int y)
{
	return a[x]>a[y] ? y : x;
}
void build(int t,int l,int r)
{
	int mid=(l+r)>>1;
	if(l==r){
		A[t]=B[t]=0;
		if(l&1) A[t]=l;
		else B[t]=l;
		return ;
	  }
	build(L(t),l,mid);
	build(R(t),mid+1,r);
	A[t]=minself(A[L(t)],A[R(t)]);
	B[t]=minself(B[L(t)],B[R(t)]);
}
int RMQ(int t,int l,int r,int l1,int r1,int *X)
{
	int mid=(l+r)>>1;
	if(l>r1 || r<l1) return 0;
	if(l>=l1&&r<=r1) return X[t];
	return minself(RMQ(L(t),l,mid,l1,r1,X),RMQ(R(t),mid+1,r,l1,r1,X));
}
int solve(int l,int r)
{
	int p,u,v,z;
	if(l>r) return 0;
	p=++m;
	if(l&1){
		u=RMQ(1,1,n,l,r,A);
		v=RMQ(1,1,n,u,r,B);
	  }
	else{
		u=RMQ(1,1,n,l,r,B);
		v=RMQ(1,1,n,u,r,A);
	  }
	C[p]=PAIR(a[u],a[v]);
	if(z=solve(l,u-1)) G[p].push_back(z);
	if(z=solve(u+1,v-1)) G[p].push_back(z);
	if(z=solve(v+1,r)) G[p].push_back(z);
	return p;
}
int main()
{
	int i; a[0]=oo;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	build(1,1,n);
	solve(1,n);
	S.insert(PAIR(C[1].first,1));
	while(!S.empty()){
		int z=(*(S.begin())).second;
		S.erase(S.begin());
		printf("%d %d ",C[z].first,C[z].second);
		for(i=0;i<G[z].size();i++)
			S.insert(PAIR(C[G[z][i]].first,G[z][i]));
	  }
	return 0;
}