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
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
const int maxn=2e5+10,logn=20;
int st[2][logn][maxn];
int p[maxn],pos[maxn];
int n,logf[maxn],tot;
std::vector<int> ed[maxn];
int co[maxn];
std::priority_queue<int,std::vector<int>,std::greater<int>> now;
struct Seq
{
    int l,r,h;
};
inline int minp(int x,int y)
{
    return p[x]<p[y]?x:y;
}
bool operator <(const Seq &a,const Seq &b)
{
    return p[a.h]<p[b.h];
}
int askmin(int l,int r,int id)
{
    if(l>r) return 0;
    int lg=logf[r-l+1];
    return minp(st[id][lg][l],st[id][lg][r-(1<<lg)+1]);
}
int work(int l,int r)
{
    int t1=askmin(l,r,l%2),t2=askmin(t1+1,r,r%2);
    co[p[t1]]=p[t2];
    if(t1>l) ed[p[t1]].push_back(work(l,t1-1));
    if(t1+1<t2-1) ed[p[t1]].push_back(work(t1+1,t2-1));
    if(t2<r) ed[p[t1]].push_back(work(t2+1,r));
    return p[t1];
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&p[i]);
        pos[p[i]]=i;
    }
    p[0]=n+1;
    logf[1]=0;
    for(int i=2;i<=n;++i) logf[i]=logf[i-1]+((i&(i-1))==0?1:0);
    for(int id=0;id<2;id++)
    {
        auto &sti=st[id];
        for(int i=1;i<=n;i++)
            sti[0][i]=(i%2==id)?i:0;
        for(int i=1;i<=logf[n];i++)
            for(int j=1;j<=n;j++)
            {
                sti[i][j]=sti[i-1][j];
                if(j+(1<<(i-1))<=n)
                    sti[i][j]=minp(sti[i][j],sti[i-1][j+(1<<(i-1))]);
            }
    }
    tot=0;
    int root=work(1,n);
    now.push(root);
    while(!now.empty())
    {
        int cur=now.top();
        printf("%d %d ",cur,co[cur]);
        now.pop();
        for(auto &i:ed[cur]) now.push(i);
    }
    return 0;
}
