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;
#define maxn 700000
#define INF 999999999
int n, a[maxn], id[maxn];

int read()
{
	int x = 0, k = 1;
	char c; c = getchar();
	while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); }
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * k;
}

struct node
{
	int x, y, l, r;
	node(int _x = 0, int _y = 0, int _l = 0, int _r = 0) 
	{ x = _x, y = _y, l = _l, r = _r; }
	friend bool operator <(const node& a, const node& b)
	{ return a.x > b.x; }
}; priority_queue <node> q;

struct tree
{
	int opt, mn[maxn];
	void Build(int p, int l, int r)
	{
		if(l == r) { mn[p] = ((l & 1) ^ opt) ? a[l] : INF; return; }
		int mid = (l + r) >> 1;
		Build(p << 1, l, mid), Build(p << 1 | 1, mid + 1, r);
		mn[p] = min(mn[p << 1], mn[p << 1 | 1]);
	}
	
	int Query(int p, int l, int r, int L, int R)
	{
		if(L > r || R < l) return INF;
		if(L <= l && R >= r) return mn[p];
		int mid = (l + r) >> 1;
		return min(Query(p << 1, l, mid, L, R), Query(p << 1 | 1, mid + 1, r, L, R));
	}
}T1, T2;

void Push(int L, int R)
{
	if(L > R) return;
	int fir, sec; 
	if(L & 1) fir = T1.Query(1, 1, n, L, R - 1), sec = T2.Query(1, 1, n, id[fir] + 1, R);
	else fir = T2.Query(1, 1, n, L, R - 1), sec = T1.Query(1, 1, n, id[fir] + 1, R);
	q.push(node(fir, sec, L, R));
}

int main()
{
	n = read();
	for(int i = 1; i <= n; i ++) a[i] = read(), id[a[i]] = i;
	T1.opt = 0, T2.opt = 1; 
	T1.Build(1, 1, n); T2.Build(1, 1, n); Push(1, n);
	while(!q.empty())
	{
		node t = q.top(); q.pop();
		int L = t.l, R = t.r;
		printf("%d %d ", t.x, t.y);
		Push(L, id[t.x] - 1);
		Push(id[t.x] + 1, id[t.y] - 1);
		Push(id[t.y] + 1, R);
	}
	puts("");
	return 0;
}