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 REP(i, n) for (int i = 0; i < int(n); ++i)
#define REPE(i, a, b) for (int i = (a); i <= int(b); ++i)
#define SZ(x) ((int)(x).size())
#define ALL(x) x.begin(), x.end()
#define PB push_back
#define EB emplace_back
using LL = long long;
using PII = pair<int, int>;
#define F first
#define S second

const int maxn = 200010;

struct Segment {
  int n, t[maxn * 2];
  void init(int n) {
    fill(t, t + maxn * 2, INT_MAX);
    this->n = n;
  }
  void set(int x, int v) {
      t[x + n] = v;
  }
  void build() {
    for (int i = n - 1; i; --i)
      t[i] = min(t[i<<1], t[i<<1|1]);
  }
  int query(int l, int r) {
    r++;
    int ret = INT_MAX;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l&1) ret = min(ret, t[l++]);
      if (r&1) ret = min(ret, t[--r]);
    }
    return ret;
  }
} s[2];
int n, a[maxn], rev[maxn];

PII query(int l, int r) {
  int a = s[l & 1].query(l, r);
  int p = rev[a];
  int b = s[~l & 1].query((p + 1), r);
  return {a, b};
}

int main() {
  scanf("%d", &n);
  s[0].init(n);
  s[1].init(n);
  REP(i, n) {
    scanf("%d", &a[i]);
    s[i & 1].set(i, a[i]);
    rev[a[i]] = i;
  }
  s[0].build();
  s[1].build();
  using T = tuple<PII, int, int>;
  priority_queue<T, vector<T>, greater<T>> q;
  q.push((T){query(0, n - 1), 0, n - 1});
  vector<int> ans;
  while (q.size()) {
    PII tp;
    int l, r;
    tie(tp, l, r) = q.top(); q.pop();
    ans.PB(tp.F);
    ans.PB(tp.S);
    int ll = rev[tp.F];
    int rr = rev[tp.S];
    if (ll > l) q.push((T){query(l, ll - 1), l, ll - 1});
    if (rr < r) q.push((T){query(rr + 1, r), rr + 1, r});
    if (ll + 1 <= rr - 1) q.push((T){query(ll + 1, rr - 1), ll + 1, rr - 1});
  }
  REP(i, n) printf("%d%c", ans[i], " \n"[i + 1 == n]);
  return 0;
}