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>
#define ll long long
#define lc (id * 2)
#define rc (id * 2 + 1)
#define mid ((l + r) >> 1)
#define fi first
#define se second

using namespace std;

const int maxN = 2e5 + 5;
int p[maxN];

struct SegmentTree {
	int e, st[maxN * 4];

	void build(int id, int l, int r) {
		if (l == r){
            st[id] = l * 2 - e;
            return;
        }
		build(lc, l, mid); build(rc, mid+1, r);
		st[id] = p[st[lc]] < p[st[rc]] ? st[lc] : st[rc];
	}

	int query(int id, int l, int r, int x, int y) {
		if (l == x && y == r)
            return st[id];
		if (y <= mid)
            return query(lc, l, mid, x, y);
		if (mid < x)
            return query(rc, mid+1, r, x, y);
		int L = query(lc, l, mid, x, mid);
		int R = query(rc,  mid+1, r, mid+1, y);
		return p[L] < p[R] ? L : R;
	}
} Tree[2];

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

priority_queue<Node> Q;
int n;

void calc(int l, int r) {
	Node res;
	res.l = l; res.r = r;
	if (l&1) {
		res.p = Tree[1].query(1, 1, n/2, (l+1)/2, (r+1)/2);
		res.q = Tree[0].query(1, 1, n/2, (res.p+2)/2, (r+1)/2);
	}
	else {
		res.p = Tree[0].query(1, 1, n/2, (l+1)/2, r/2);
		res.q = Tree[1].query(1, 1, n/2, (res.p+2)/2, (r+1)/2);
	}
	res.a = p[res.p]; res.b = p[res.q];
	Q.push(res);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(); cout.tie();
	cin >> n;

	Tree[0].e = 0; Tree[1].e = 1;

	for(int i = 1; i <= n; ++i)
        cin >> p[i];

	Tree[0].build(1, 1, n/2);
	Tree[1].build(1, 1, n/2);
	calc(1, n);

	while (!Q.empty())
    {
		tmp = Q.top();
        Q.pop();
		cout << tmp.a << " " << tmp.b << " ";
		if (tmp.l < tmp.p) calc(tmp.l, tmp.p-1);
		if (tmp.p + 1 < tmp.q) calc(tmp.p+1, tmp.q-1);
		if (tmp.q < tmp.r) calc(tmp.q+1, tmp.r);
	}
	return 0;
}
