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 <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
#include <queue>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 2e5+5;
int n, m, p[N], q[N], lg[N], ans[N];
vector<int> to[N]; pair<int, int> s[N];
priority_queue<pair<int, int> > h;
struct ST
{
    int _[18][N];
    void build(int k)
    {
        for(int i = 2-k; i <= n; i += 2) _[0][i] = p[i];
        for(int i = 2-(k^1); i <= n; i += 2) _[0][i] = n+1;
        for(int i = 1, m = lg[n]; i <= m; ++i)
            for(int j = 1; j+(1<<i)-1 <= n; ++j)
                _[i][j] = min(_[i-1][j], _[i-1][j+(1<<(i-1))]);
    }
    int ask(int l, int r)
    {
        int i = lg[r-l+1];
        return min(_[i][l], _[i][r-(1<<i)+1]);
    }
}f[2];
int solve(int l, int r)
{
    int a = f[l&1].ask(l, r), b = f[(l&1)^1].ask(q[a]+1, r), c = ++m; s[c] = make_pair(a, b);
    if(l != q[a]) to[c].push_back(solve(l, q[a]-1));
    if(q[a]+1 != q[b]) to[c].push_back(solve(q[a]+1, q[b]-1));
    if(q[b] != r) to[c].push_back(solve(q[b]+1, r));
    return c;
}
int main()
{
    n = read();
    for(int i = 1; i <= n; ++i) p[i] = read(), q[p[i]] = i;
    for(int i = 2; i <= n; ++i) lg[i] = lg[i>>1]+1;
    f[0].build(0), f[1].build(1), solve(1, n), m = 0, h.push(make_pair(-s[1].first, 1));
    while(h.size())
    {
        int x = h.top().second; h.pop(); ans[++m] = s[x].first, ans[++m] = s[x].second;
        for(int i = 0; i < to[x].size(); ++i) h.push(make_pair(-s[to[x][i]].first, to[x][i]));
    }
    for(int i = 1; i <= n; ++i) printf("%d ", ans[i]); puts("");
    return 0;
}