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 pi 3.1415926535897932384626
using namespace std;
      
struct P{
  int x,y;
  bool operator < (const P &a )const{
    //if(y!=a.y)
    return y>a.y;
  };
};

int a,b,c,d,i,k,n,m,e,dx[10]={1,0,-1,0,1,1,-1,-1},dy[10]={0,1,0,-1,1,-1,1,-1};
int o[200110];
int l[1];
int j[1];

long long x,y,z,mod=1000000007;
//string r;
char r[2][66];

P u[555551];
priority_queue<P> q;
//stack<int> s;
set<int> s;
map<int,int> p;
vector<int> v;

bool as(P a,P b)
{
  return a.x<b.x;
}

P mm(P a,P b)
{
  P k;
  if(o[a.x]<o[b.x]) k.x=a.x;
  else k.x=b.x;
  if(o[a.y]<o[b.y]) k.y=a.y;
  else k.y=b.y;
  return k;
}

int f(int n,int m)
{
  n++,m--;
  int p=n;
  P k={0,0};
  for(;n<m;)
  {
    if(n%2) k=mm(k,u[n++]);
    else if(m%2==0) k=mm(k,u[m--]);
    else n/=2,m/=2;
  }
  //printf("!!%d %d %d\n",i,mm(k,u[n]).x,mm(k,u[n]).y);
  if(p%2) return mm(k,u[n]).x;
  return mm(k,u[n]).y;
}

int main()
{
  scanf("%d",&a);
  for(i=1;i<a;i*=2);
  o[0]=mod;
  for(int t=1;t<=a;t++)
  {
    scanf("%d",&n);
    o[t]=n;
    if((t+i-1)%2) u[t+i-1]={t,0};
    else u[t+i-1]={0,t};
  }
  for(int t=i-1;t;t--)
  u[t]=mm(u[t*2],u[t*2+1]);
  s.insert(0);
  s.insert(a+1);
  e=f(i-1,a+i);
  q.push({e,o[e]});
  for(;q.size();)
  {
    P k=q.top();
    q.pop();
    printf("%d ",k.y);
    m=f(k.x+i-1,(*s.upper_bound(k.x))+i-1);
    printf("%d ",o[m]);
    s.insert(k.x);
    s.insert(m);
    if(k.x+1<m)
    {
      d=f(k.x+i-1,m+i-1);
      //puts("#");
      //printf("@@%d %d %d\n",d,k.x,m);
      q.push({d,o[d]});
    }
    set<int>::iterator c=s.find(k.x);
    c--;
    if((*c)+1<k.x)
    {
      //puts("$");
      d=f((*c)+i-1,k.x+i-1);
      q.push({d,o[d]});
    }
    c=s.find(m);
    c++;
    if(m+1<(*c))
    {
      //puts("$");
      d=f(m+i-1,(*c)+i-1);
      q.push({d,o[d]});
    }
  }
}