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>
#define rep(a, b, c) for(int a = (b); a <= (c); ++ a)
#define per(a, b, c) for(int a = (b); a >= (c); -- a)
using namespace std;
template <class T> void rd(T &x){
  x = 0; int f = 1; char ch = getchar();
  while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
  while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
  x *= f;
}

typedef pair <int, int> pii;
#define fi first
#define se second

const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 5;
pii mi[21][maxn << 1];
int n, m;
int lg[maxn], val[maxn], ans[maxn];

struct node{ int v, l, r, x, y;
  bool operator < (const node &b) const {
	return v < b.v; 
  }
};

priority_queue <node> q;

pii query(int l, int r){
  int t = lg[r - l + 1];
  return min(mi[t][l], mi[t][r - (1 << t) + 1]);
}

void push(int l, int r){
  if(l > r) return ;
  pii x = query(l, r);
  pii y = query(x.se + 1, r + 1);
  q.push((node){-x.fi, l, r, x.se, y.se});
}

int main(){
  rd(n);
  rep(i, 1, n) rd(val[i]), mi[1][i] = pii(val[i], i);
  rep(i, 2, n) lg[i] = lg[i >> 1] + 1;
  rep(i, 2, lg[n]) rep(j, 1, n)
	mi[i][j] = min(mi[i - 1][j], mi[i - 1][j + (1 << i - 1)]);
  push(1, n);
  while(!q.empty()){
	node t = q.top(); q.pop();
	ans[++ m] = val[t.x];
	ans[++ m] = val[t.y];
	push(t.l, t.x - 1);
	push(t.x + 1, t.y - 1);
	push(t.y + 1, t.r);
  }
  rep(i, 1, m) printf("%d ", ans[i]);
  return 0;
}