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<cstdio>
#include<vector>
#include<queue>
#define MN 200000
#define N 262144
using namespace std;
inline 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;
}
struct data{int x,y,id;
	bool operator <(const data&b)const{return x>b.x;}
}s[MN+5];
priority_queue<data> q;vector<int> v[MN+5];
int n,a[MN+5],T[N*2+5],t[N*2+5],num=0;
inline int Merge(int x,int y){return a[x]<a[y]?x:y;}
int Query(int*T,int l,int r)
{
	int res=0;
	for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1)	
	{
		if(~l&1) res=Merge(res,T[l+1]);	
		if( r&1) res=Merge(res,T[r-1]);
	}
	return res;
}
int Solve(int l,int r)
{
	int x=0,y=0,z=++num;
	if(l&1) x=Query(T,l,r-1),y=Query(t,x,r); 
	else    x=Query(t,l,r-1),y=Query(T,x,r);
	s[z]=(data){a[x],a[y],z};
	if(x!=l) v[z].push_back(Solve(l,x-1));
	if(r!=y) v[z].push_back(Solve(y+1,r));
	if(x!=y-1) v[z].push_back(Solve(x+1,y-1));
	return z;
} 
int main()
{
	n=read();a[0]=1e9;
	for(int i=1;i<=n;++i) a[i]=read(),(i&1)?T[i+N]=i:t[i+N]=i;
	for(int i=N;i;--i) T[i]=Merge(T[i<<1],T[i<<1|1]),t[i]=Merge(t[i<<1],t[i<<1|1]);
	int id=Solve(1,n);q.push(s[id]);
	while(!q.empty())
	{
		data x=q.top();q.pop();
		printf("%d %d ",x.x,x.y);	
		for(int i=0;i<v[x.id].size();++i) q.push(s[v[x.id][i]]);
	}
	return 0;
}