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<algorithm>
#include<vector>
#include<queue>
using namespace std;
vector<pair<int,int> >ans;
vector<int>G[1<<17];
int N;
int A[2<<17];
int bit[2<<17];
int table[3][20][2<<17];
int query(int L,int R,int w)
{
	int b=bit[R-L];
	int x=table[w][b][L],y=table[w][b][R-(1<<b)];
	return x==-1?y:y==-1?x:A[x]<A[y]?x:y;
}
int dfs(int L,int R)
{
	int mid=query(L,R,L%2?2:1),mmid=query(mid+1,R,mid%2?1:2),id=ans.size();
	ans.push_back(make_pair(-A[mid],-A[mmid]));
	if(L+1<mid)
	{
		G[id].push_back(dfs(L,mid));
	}
	if(mid+2<mmid)
	{
		G[id].push_back(dfs(mid+1,mmid));
	}
	if(mmid+2<R)
	{
		G[id].push_back(dfs(mmid+1,R));
	}
	return id;
}
int main()
{
	cin>>N;
	for(int i=0;i<N;i++)
	{
		cin>>A[i];
		table[0][0][i]=i;
		table[i%2?2:1][0][i]=i;
		table[i%2?1:2][0][i]=-1;
	}
	for(int i=2;i<=N;i++)bit[i]=bit[i>>1]+1;
	for(int w=0;w<3;w++)
	{
		for(int k=1;k<20;k++)
		{
			for(int i=0;i<=N-(1<<k);i++)
			{
				int x=table[w][k-1][i],y=table[w][k-1][i+(1<<k-1)];
				table[w][k][i]=x==-1?y:y==-1?x:A[x]<A[y]?x:y;
			}
		}
	}
	int root=dfs(0,N);
	priority_queue<pair<pair<int,int>,int> >P;
	P.push(make_pair(ans[root],root));
	while(!P.empty())
	{
		int id=P.top().second;
		pair<int,int>p=P.top().first;
		P.pop();
		cout<<-p.first<<" "<<-p.second<<" ";
		for(int v:G[id])
		{
			P.push(make_pair(ans[v],v));
		}
	}
	cout<<endl;
}