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;

typedef long long ll;

ll N;
const ll L = 20;
typedef pair<ll, ll> Data;
vector<vector<Data>> Min;
typedef tuple<Data, ll, ll> Entry;
priority_queue<Entry, vector<Entry>, greater<Entry>> Que;

Data min_range(ll i, ll j) {
  assert(i < j);
  assert((j - i) % 2 == 0);
  ll l = 0;
  while ((1 << l) * 2 * 2 < j - i) ++l;
  ll j2 = j - (1 << l) * 2;
  assert(i <= j2);
  return min(Min[l][i], Min[l][j2]);
}
void push(ll i, ll j) {
  if (i < j) Que.push(Entry(min_range(i, j), i, j));
}
int main() {
  cin >> N;
  Min.resize(L);
  for (auto &min : Min) min.resize(N + 2);
  for (ll i = 0; i < N; ++i) {
    ll p;
    cin >> p;
    Min[0][i] = Data(p, i);
  }
  Min[0][N] = Min[0][N + 1] = Data(1ll << 60, -1);
  for (ll l = 1; l < L; ++l)
    for (ll i = 0; i < N + 2; ++i) {
      Min[l][i] = min(Min[l - 1][i],
                      Min[l - 1][i + min(1ll << l, (N + 1 - i) / 2 * 2)]);
    }
  push(0, N);
  bool first = true;
  while (!Que.empty()) {
    Data pk;
    ll i, j, p, k;
    tie(pk, i, j) = Que.top();
    tie(p, k) = pk;
    Que.pop();
    ll q, l;
    tie(q, l) = min_range(k + 1, j + 1);
    cout << (first ? "" : " ") << p << " " << q;
    first = false;
    push(k + 1, l);
    push(i, k);
    push(l + 1, j);
  }
  cout << endl;
  return 0;
}