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>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;

const int MN = 2e5+5;
const int MOD = 1e9+7;
const int INF = 1e9;

int N,A[MN],I[MN],cnt;
vector<int> G[MN];
pii P[MN<<2],E[MN];
priority_queue<pii,vector<pii>,greater<pii>> PQ;

pii cal(pii X, pii Y)
{
	pii P;
	P.va = A[X.va]<A[Y.va] ? X.va : Y.va;
	P.vb = A[X.vb]<A[Y.vb] ? X.vb : Y.vb;
	return P;
}

void init(int s, int e, int i)
{
	if(s==e){
		if(s%2) P[i].va = s;
		else P[i].vb = s;
		return;
	}
	int m = (s+e)/2;
	init(s,m,i<<1);
	init(m+1,e,i<<1|1);
	P[i] = cal(P[i<<1],P[i<<1|1]);
}

pii get(int s, int e, int x, int y, int i)
{
	if(e<x||y<s) return pii(0,0);
	if(x<=s&&e<=y) return P[i];
	int m = (s+e)/2;
	return cal(get(s,m,x,y,i<<1),get(m+1,e,x,y,i<<1|1));
}


int solve(int s, int e)
{
	if(s>e) return 0;
	int l,r,a,b,c;
	if(s%2){
		l = get(1,N,s,e-1,1).va;
		r = get(1,N,l+1,e,1).vb;
	}
	else{
		l = get(1,N,s,e-1,1).vb;
		r = get(1,N,l+1,e,1).va;	
	}
	E[++cnt] = pii(A[l],A[r]);
	int x = cnt;
	a = solve(s,l-1);
	b = solve(l+1,r-1);
	c = solve(r+1,e);
	if(a) G[x].push_back(a);
	if(b) G[x].push_back(b);
	if(c) G[x].push_back(c);
	I[a]++;
	I[b]++;
	I[c]++;
	return x;
}

int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> N;
    A[0] = MN;
    for(int i=1; i<=N; i++){
    	cin >> A[i];
    }
    init(1,N,1);
    int x = solve(1,N);
    PQ.emplace(E[x].va,x);
    while(PQ.size()){
    	x = PQ.top().vb;
    	PQ.pop();
    	for(int v:G[x]){
    		I[v]--;
    		if(!I[v]) PQ.emplace(E[v].va,v);
    	}
    	cout << E[x].va << ' ' << E[x].vb << ' ';
    }
}