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 = 200010;
int a[N], n;
int rmq[N][22];
inline void chkmin(int& a, int b){
	if(a > b) a = b;
}
int toid[N];
int get(int l, int r){
	int m = 31 - __builtin_clz(r - l + 1);
	return min(rmq[l][m], rmq[r - (1 << m) + 1][m]);
}
struct Node{
	int l, r;
	int v1, v2;
	Node(int l = 0, int r = 0) : l(l), r(r){}
	void setminv(){
		v1 = get(l, r);
		v2 = get(toid[v1] + 1, r + 1);
	}
	bool operator<(const Node& an) const{
		return v1 > an.v1;
	}
};
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i], toid[a[i]] = i;
	for(int i = 1; i <= n; i++) rmq[i][0] = rmq[i][1] = a[i];
	for(int j = 2; j < 22; j++)
		for(int i = 1; i <= n; i++){
			int ni = i + (1 << (j - 1));
			rmq[i][j] = rmq[i][j - 1];
			if(ni <= n) chkmin(rmq[i][j], rmq[ni][j - 1]);
		}
	priority_queue<Node> pq;
	Node st(1, n); st.setminv();
	pq.push(st);
	vector<int> sol;
	while(!pq.empty()){
		Node top = pq.top(); pq.pop();
		sol.push_back(top.v1), sol.push_back(top.v2);
		int id1 = toid[top.v1], id2 = toid[top.v2];
		int l = top.l, r = top.r;
		if(l < id1){
			Node psh(l, id1 - 1); psh.setminv();
			pq.push(psh);
		}
		if(id2 - id1 > 1){
			Node psh(id1 + 1, id2 - 1); psh.setminv();
			pq.push(psh);
		}
		if(id2 < r){
			Node psh(id2 + 1, r); psh.setminv();
			pq.push(psh);
		}
	}
	for(int i = 0; i < sol.size(); i++)
		cout << sol[i] << " \n"[i == sol.size() - 1];
	return 0;
}