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;
const int N = 3e5 + 10, inf = 1e9 ;
int tr[N<<1][2],a[N],book[N];
int n,ans=0,M;

void build(int n) {
	memset(tr,38,sizeof(tr));
	for(M=1;M<=n+1;M<<=1);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),book[a[i]]=i,tr[M+i][i&1]=a[i];
	for(int i=M-1;i>=1;i--)
		for(int k=0;k<2;k++)
			tr[i][k]=min(tr[i<<1][k],tr[i<<1|1][k]);
}


struct Node {
	int l,r,st,L,R;
	bool operator < (const Node &rhs) const {
		return a[L]>a[rhs.L];
	}
};

priority_queue<Node> q;

int Q(int s,int t,int st,int ans=inf) {
	for(s=s+M-1,t=t+M+1;s^t^1;s>>=1,t>>=1) {
		if(~s&1) ans=min(ans,tr[s^1][st]);
		if(t&1) ans=min(ans,tr[t^1][st]);
	}
	return ans;
}

inline void A(int l,int r,int st) {
	if(l>r) return ;
	int s=book[Q(l,r,st)],t=book[Q(s,r,st^1)];
	tr[s+M][st]=inf,tr[t+M][st^1]=inf;
	q.push((Node){l,r,st,s,t});
}

int main() {
	cin>>n;
	build(n);
	A(1,n,1);
	while(!q.empty()) {
		Node u=q.top();
		q.pop();
		printf("%d %d ",a[u.L],a[u.R]);
		A(u.l,u.L-1,u.st);A(u.R+1,u.r,u.st);A(u.L+1,u.R-1,u.st^1);
	}
}