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
#include<bits/stdc++.h>

#define up(l,r,i) for(int i=l;i<=r;i++)
#define dn(l,r,i) for(int i=l;i>=r;i--)

using namespace std;

typedef long long LL;
const int INF =2147483647;
int qread(){
	int w=1,c,ret;
	while((c=getchar())> '9'||c< '0')
	w=(c=='-'?-1:1); ret=c-'0';
	while((c=getchar())>='0'&&c<='9')
	ret=ret*10+c-'0';
	return ret*w;
}

const int MAXN =2e5+3,MAXM=18 +3;
int n,P[MAXN];
class ST_Table{
	public:
		int data[MAXM][MAXN],pos[MAXM][MAXN];
		void buld(bool type){
			up(1,n,i) data[0][i]=INF;
			up(1,n/2,i) data[0][(i<<1)-type]=P[(i<<1)-type],
						pos[0][(i<<1)-type]=(i<<1)-type;
			up(1,18,i) up(1,n,j){
				if(j+(1<<i)-1>n) break;
				pos[i][j]=data[i-1][j]<data[i-1][j+(1<<i-1)]?
				pos[i-1][j]:pos[i-1][j+(1<<i-1)];
				data[i][j]=min(data[i-1][j],data[i-1][j+(1<<i-1)]);
			}
		}
		void gtmn(int L,int R,int &mn,int &ps){
			int delta=R-L+1,cnt=0;
			while((1<<cnt)<=delta) cnt++; cnt--;
			ps=(data[cnt][L]<data[cnt][R-(1<<cnt)+1]?
				pos[cnt][L]:pos[cnt][R-(1<<cnt)+1]);
			mn=min(data[cnt][L],data[cnt][R-(1<<cnt)+1]);
		}
}ST[2];
class Node{
	public:
		int L,R,t1,t2,p1,p2;
		Node(int _L,int _R){
			bool type=!(_L&1); L=_L,R=_R;
			ST[ type].gtmn(L,R,t1,p1);
			ST[!type].gtmn(p1+1,R,t2,p2);
		}
		bool operator <(const Node t)const{
			return t1==t.t1?t2<t.t2:t1<t.t1;
		}
		bool operator >(const Node t)const{
			return t1==t.t1?t2>t.t2:t1>t.t1;
		}
};
priority_queue <Node,vector<Node>,greater<Node> >pq;
void calc(){
	pq.push(Node(1,n));
	while(!pq.empty()){
		Node t=pq.top(); pq.pop();
		printf("%d %d ",t.t1,t.t2);
		if(t.L!=t.p1) 	pq.push(Node(t.L,t.p1-1));
		if(t.p1+1!=t.p2)pq.push(Node(t.p1+1,t.p2-1));
		if(t.R!=t.p2)	pq.push(Node(t.p2+1,t.R));
	}
}
int main(){
	n=qread();
	up(1,n,i) P[i]=qread();
	ST[0].buld(1),ST[1].buld(0);
	calc();
	return 0;
}
