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 N 200010
using namespace std;
int n;
int a[N]={};
struct node{
  int l,r,u,v;
  friend bool operator <(const node x,const node y){return a[x.u]>a[y.u];}
};
struct rode{
  int l,r;
  int x;
}t[N<<2][2]={};
priority_queue<node>q;
inline int read()
{
	int s = 0, w = 1;
	char c = getchar();
	while ((c<'0' || c>'9') && c != '0')c = getchar();
	if (c == '-')w = -1, c = getchar();
	while (c <= '9'&&c >= '0')s = (s << 3) + (s << 1) + c - '0', c = getchar();
	return s * w;
}
inline void push(int p)
{
  for(int i=0;i<=1;++i)
    if(a[t[p<<1][i].x]<a[t[p<<1|1][i].x])
      t[p][i].x=t[p<<1][i].x;
    else t[p][i].x=t[p<<1|1][i].x;
}
void build(int p,int l,int r)
{
  if(l==r){t[p][l%2].x=l;return ;}
  int mid=(l+r)>>1;
  build(p<<1,l,mid);build(p<<1|1,mid+1,r);
  push(p);
}
inline int ask(int p,int l,int r,int tl,int tr,int c)
{
  if(tl==l&&r==tr)return t[p][c].x;
  int mid=(l+r)>>1;
  if(tr<=mid)return ask(p<<1,l,mid,tl,tr,c);
  else if(tl>mid)return ask(p<<1|1,mid+1,r,tl,tr,c);
  else{
    int k=ask(p<<1,l,mid,tl,mid,c),kk=ask(p<<1|1,mid+1,r,mid+1,tr,c);
    if(a[k]<a[kk])return k;else return kk;
  }
}
inline void ins(int l,int r)
{
  int c=ask(1,1,n,l,r,l%2);
  int d=ask(1,1,n,c+1,r,r%2);
  node t;
  t.l=l;t.r=r;t.u=c;t.v=d;
  q.push(t);
}
int ans[N]={},cnt=0;
int main()
{
  n=read();a[0]=0x3f3f3f3f;
  for(int i=1;i<=n;++i)a[i]=read();
  build(1,1,n);
  ins(1,n);
  while(!q.empty())
  {
    node t=q.top();q.pop();
    ans[++cnt]=a[t.u];ans[++cnt]=a[t.v];
    if(t.u!=t.l)ins(t.l,t.u-1);
    if(t.u+1!=t.v)ins(t.u+1,t.v-1);
    if(t.v!=t.r)ins(t.v+1,t.r);
  }
  // printf("%d\n",cnt);
  for(int i=1;i<=cnt;++i)printf("%d ",ans[i]);
  return 0;
}