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>
using namespace std; 
#define ll long long 
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define ld long double
int const M=2e5+10,M2=1e7+10,mod=1e9+7,inf=1e9+10;
vector<int>ans;
int id[M],n,a[M];
set<pair<pii,pii> >st;
struct se
{
	int fard,zoj;
};
se seg[M*4];
void build(int l,int r,int node)
{
	if(r-l==1)
	{
		if(l%2)seg[node].fard=a[l],seg[node].zoj=inf;
		else seg[node].zoj=a[l],seg[node].fard=inf;
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,node*2);
	build(mid,r,node*2+1);
	seg[node].zoj=min(seg[node*2].zoj,seg[node*2+1].zoj);
	seg[node].fard=min(seg[node*2].fard,seg[node*2+1].fard);
}
int get(int l,int r,int st,int en,int t,int node)
{
	if(st<=l && r<=en)
	{
		if(t)return seg[node].fard;
		return seg[node].zoj;
	}
	if(st>=r || l>=en)return inf;
	int mid=(l+r)>>1;
	return min(get(l,mid,st,en,t,node*2),get(mid,r,st,en,t,node*2+1));
}
void add(int l,int r)
{
	if(r<l)return;
	int tmp=get(1,n+1,l,r+1,1-(r%2),1);
	int x=id[tmp];
	int tmp2=get(1,n+1,x+1,r+1,1-(x%2),1);
	st.insert(mp(mp(tmp,tmp2),mp(l,r)));
}
int32_t main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);	
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],id[a[i]]=i;
	build(1,n+1,1);
	add(1,n);
	while(st.size())
	{
		pair<pii,pii> tmp=*st.begin();
		st.erase(tmp);
		ans.pb(tmp.F.F);
		ans.pb(tmp.F.S);
		int l=tmp.S.F,r=tmp.S.S;
		int x1=id[tmp.F.F];
		int x2=id[tmp.F.S];
		add(l,x1-1);
		add(x1+1,x2-1);
		add(x2+1,r);
	}
	for(int i=0;i<ans.size();i++)cout<<ans[i]<<" ";
}