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>
using namespace std;
const int N = 200100;
const int inf = 233333333;

struct Node{
	int x, l, r;
	Node(){}
	Node(int a, int b, int c) {x = a, l = b, r = c;}
	bool operator < (const Node & a) const{
		return x > a.x;
	}
};

int n, nn, M;
int T1[N << 3], T2[N << 3], seq[N]; 
priority_queue<Node> q;

int Min(int x, int y){if(seq[x] > seq[y]) return y; return x;}

int Query(int x, int y, int * T){
	if(x > y) return 0;
	int res = 0;
	for(x = x + M - 1, y = y + M + 1; x ^ y ^ 1; x >>= 1, y >>= 1){
		if(~ x & 1) res = Min(res, T[x ^ 1]);
		if(  y & 1) res = Min(res, T[y ^ 1]);
	}
	return res;
}

int Query(int x, int y, int f){
	if(f & 1) return Query(x, y, T1);
	return Query(x, y, T2);
}

void Change(int x, int t, int * T){
	x += M;
	T[x] = t;
	for(x >>= 1; x; x >>= 1) T[x] = Min(T[x << 1], T[x << 1 | 1]);
	return;
}

int main(){
	seq[0] = inf;
	scanf("%d", & n);
	for(int i = 1; i <= n; i ++)
		scanf("%d", &seq[i]);
	for(M = 1; M <= n + 1; M <<= 1);
	for(int i = 1; i <= n; i += 2) T1[i + M] = i;
	for(int i = 2; i <= n; i += 2) T2[i + M] = i;
	for(int i = M - 1; i; i --) T1[i] = Min(T1[i << 1], T1[i << 1| 1]), T2[i] = Min(T2[i << 1], T2[i << 1 | 1]);
	q.push(Node(seq[Query(1, n, 1)], 1, n));
	Node k;
	int x, y;
	while(!q.empty()){
		k = q.top();
		q.pop();
		x = Query(k.l, k.r, k.l & 1);
		y = Query(x, k.r, !(k.l & 1));
		printf("%d %d ", seq[x], seq[y]);
		if(k.l < x) q.push(Node(seq[Query(k.l, x - 1, k.l & 1)], k.l, x - 1));
		if(y - x >= 2) q.push(Node(seq[Query(x + 1 , y - 1, (x + 1) & 1)], x + 1, y - 1));
		if(y < k.r) q.push(Node(seq[Query(y + 1, k.r, (y + 1) & 1)], y + 1, k.r));
	}
	
	return 0;
}