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:
%:pragma GCC optimize(3)
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;

int n, a[201000], pos[201000], b[201000], l[200100], r[200100], M[19][200100], p[19][200100];

int Query(int l, int r, int ty) {
	int t = (int)log2((r - l + 2) / 2);
	if((r - l) & 1) r--;
//	printf("%d : %d %d\n", t, p[t][l], p[t][r - (1 << t)]);
//	system("pause");
	int mi = min(M[t][l], M[t][r - (1 << (t + 1)) + 2]);
	if(!ty) return mi;
	else return M[t][l] == mi ? p[t][l] : p[t][r - (1 << (t + 1)) + 2];
} 

struct Node{
	int l, r;
	Node(int l = 0, int r = 0) : 
		l(l), r(r) {}
	bool operator < (const Node &b) const {
		return Query(l, r, 0) > Query(b.l, b.r, 0);
	}
};

void Read(int &x) {
	char ch = getchar(); x = 0;
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
}

priority_queue<Node> q;

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		Read(a[i]);
		M[0][i] = a[i];
		p[0][i] = i;
	}
	
	for(int i = 1; i <= 18; i++)
		for(register int j = 1; j <= n - (1 << (i + 1)) + 2; j++) {
			M[i][j] = min(M[i - 1][j], M[i - 1][j + (1 << i)]);
			p[i][j] = M[i][j] == M[i - 1][j] ? p[i - 1][j] : p[i - 1][j + (1 << i)];
		}

	q.push(Node(1, n));
	while(!q.empty()) {
		Node now = q.top(); q.pop();
		int mi = Query(now.l, now.r, 1);
		int mii = Query(mi + 1, now.r, 1);
		printf("%d %d ", a[mi], a[mii]);
		
		if(mii - mi > 1) q.push(Node(mi + 1, mii - 1));
		if(mi != now.l) q.push(Node(now.l, mi - 1));
		if(mii != now.r) q.push(Node(mii + 1, now.r));
	}
	return 0;
}
/*
6
1 4 5 2 3 6
12 
9 8 6 10 12 4 1 3 11 5 2 7
*/