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 <cstdio>
#include <cctype>
#include <algorithm>
#define repu(i,x,y) for (int i=x; i<=y; ++i)
#define repd(i,x,y) for (int i=x; i>=y; --i)
using namespace std;

int n,a[200100],f[20][200100][2],log_[200100],top;
struct data
{
    int l,r,x,y;
    bool operator<(const data &t) const
    {
        return a[x]>a[t.x] || a[x]==a[t.x] && a[y]>a[t.y];
    }
} heap[100100];

int minp(int x,int y)
{
    return a[x]<a[y]?x:y;
}

int getint()
{
    char ch;
    while (!isdigit(ch=getchar()));
    int x=ch-'0';
    for (; isdigit(ch=getchar()); x=x*10+ch-'0');
    return x;
}

int query(int l,int r,int t)
{
    int k=log_[r-l+1];
    return minp(f[k][l][t],f[k][r-(1<<k)+1][t]);
}

void insert(int l,int r)
{
    if (l>r)
        return;
    int x=query(l,r,l&1),y=query(x+1,r,r&1);
    heap[++top]=(data){l,r,x,y},push_heap(heap+1,heap+1+top);
}

int main()
{
    n=getint(),a[0]=1<<30;
    repu(i,1,n)
        a[i]=getint();
    repu(i,1,n)
        f[0][i][i&1]=i;
    repu(i,2,n)
        log_[i]=log_[i>>1]+1;
    repu(i,1,log_[n])
        repd(j,n-(1<<i)+1,1)
        {
            f[i][j][0]=minp(f[i-1][j][0],f[i-1][j+(1<<i-1)][0]);
            f[i][j][1]=minp(f[i-1][j][1],f[i-1][j+(1<<i-1)][1]);
        }
    insert(1,n);
    while (top)
    {
        data t=heap[1];
        pop_heap(heap+1,heap+1+top--);
        printf("%d %d ",a[t.x],a[t.y]);
        insert(t.l,t.x-1),insert(t.x+1,t.y-1),insert(t.y+1,t.r);
    }
    return 0;
}