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<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#define maxx 2000000000
#define maxn 200009
using namespace std;
priority_queue<int>q;
int to[maxn],f[maxn],n,wei[maxn],f1[maxn][20],f2[maxn][20];
vector<int>g[maxn];
void dfs(int lef,int righ,int fa)
{
  int w1,w2,len;
  if (lef>=righ) return;
  len=trunc(log(righ-lef+1)/log(2));
  if ((lef%2)==1) w1=min(f1[lef][len],f1[righ-(1<<len)+1][len]);
  else  w1=min(f2[lef][len],f2[righ-(1<<len)+1][len]);
  len=trunc(log(righ-wei[w1]+1)/log(2));
  if ((lef%2)==1) w2=min(f2[wei[w1]][len],f2[righ-(1<<len)+1][len]);
  else w2=min(f1[wei[w1]][len],f1[righ-(1<<len)+1][len]);
  dfs(lef,wei[w1]-1,fa);
  dfs(wei[w2]+1,righ,fa);
  dfs(wei[w1]+1,wei[w2]-1,w1);
  f[w1]=fa; to[w1]=w2;
  g[fa].push_back(w1);
}
int main()
{
  scanf("%d",&n);
  int x;
  for (int i=1;i<=n;i++) f1[i][0]=f2[i][0]=maxx;
  for (int i=1;i<=n;i++) 
  {
    scanf("%d",&x);
    wei[x]=i;
    if (i%2==1) f1[i][0]=x;
    else f2[i][0]=x;
  }
  for (int j=1;(1<<j)<=n;j++)
  for (int i=(n-(1<<j)+1);i>=1;i--)
  {
   f1[i][j]=min(f1[i][j-1],f1[i+(1<<(j-1))][j-1]);
   f2[i][j]=min(f2[i][j-1],f2[i+(1<<(j-1))][j-1]);
  }
  dfs(1,n,0);
  for (int i=0;i<g[0].size();i++) q.push(-g[0][i]);
  bool fg=1;
  while (!q.empty())
  {
    int now=-q.top();q.pop();
	if (fg) printf("%d %d",now,to[now]);
	else printf(" %d %d",now,to[now]);
	fg=0;
	for (int i=0;i<g[now].size();i++)
	q.push(-g[now][i]);	
  } 
  return 0;
}