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<set>
using namespace std;
int n;
int a[200010];
int ind[200010];
vector<int>ans;
set<int>st;
set<int>bar;
int mnum;
struct segment_tree{
	int mn[1<<20],N,sz;
	void init()
	{
		N=1;
		while(N<n)N*=2;
		for(int i=0;i<N*2-1;i++)mn[i]=1e9;
	}
	void pushup(int x)
	{
		while(x>0)
		{
			x=(x-1)>>1;
			mn[x]=min(mn[(x<<1)+1],mn[(x<<1)+2]);
		}
	}
	void ins(int x)
	{
		int pos=(sz++)+N-1;
		mn[pos]=x;
		pushup(pos);
	}
	int query(int a,int b,int k,int l,int r)
	{
		if(a>=r || b<=l)return 1e9;
		if(a<=l && b>=r)return mn[k];
		return min(query(a,b,(k<<1)+1,l,(l+r)>>1),query(a,b,(k<<1)+2,(l+r)>>1,r));
	}
}s[2];
int main()
{
	scanf("%d",&n);
	s[0].init();
	s[1].init();
	for(int i=1;i<=n;i++)
	{
		scanf("%d",a+i);
		ind[a[i]]=i;
	}
	for(int i=1;i<=n;i++)
	{
		s[i&1].ins(a[i]);
		s[(i&1)^1].ins(1e9);
	}
	st.insert(s[1].query(0,n-1,0,0,s[1].N));
	bar.insert(0);
	bar.insert(n+1);
	int l=0; 
	while(l<n)
	{
		mnum=*st.begin();
		ans.push_back(mnum);
		int w=ind[mnum];
		int mnn=1e9;
		set<int>::iterator it1=bar.lower_bound(w);
		set<int>::iterator it2=it1;
		it1--;
		mnn=min(mnn,s[(w&1)^1].query(w,(*it2)-1,0,0,s[(w&1)^1].N));
		ans.push_back(mnn);
		st.erase(st.begin());
		int tt=s[w&1].query((*it1),w-1,0,0,s[w&1].N);
		if(tt!=1e9)st.insert(tt);
		tt=s[(w&1)^1].query(w,ind[mnn]-1,0,0,s[(w&1)^1].N);
		if(tt!=1e9)st.insert(tt);
		tt=s[w&1].query(ind[mnn],(*it2)-1,0,0,s[w&1].N);
		if(tt!=1e9)st.insert(tt);
		bar.insert(w);
		bar.insert(ind[mnn]);
		l+=2;
	}
	for(int i=0;i<n;i++)printf("%d ",ans[i]);
	return 0;
}