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> 
using namespace std;
#define N 1000100
#define k 100000000 
#define F (rt<<1)
#define s int
#define G (rt<<1|1)
#define o first
#define u second
#define I push_back
#define K return
#define X void
struct J{s a,b,H;}p[N];typedef pair<s,s> pa;bool operator < (J x,J y){if (x.a==y.a) K x.b>y.b;K x.a>y.a;}priority_queue<J> q;s n,i,a[N],A,t[N];pa m[N<<3];vector
 e[N],ans;X E(pa &x,pa y) {x.o=min(x.o,y.o),x.u=min(x.u,y.u);}X c(s rt,s l,s r){m[rt].o=k;m[rt].u=k;if (l==r){if (l&1) m[rt].o=a[l];else m[rt].u=a[l];K ;}s D=(l+r)/2;c(F,l,D);c(G,D+1,r);E(m[rt],m[F]),E(m[rt],m[G]);}pa b(s rt,s l,s r,s x,s y){if (x<=l&&r<=y) K m[rt];s D=(l+r)/2;pa C=make_pair(k,k);if(x<=D) E(C,b(F,l,D,x,y));if (y>=D+1) E(C,b(G,D+1,r,x,y));K C;}s d(s l,s r){s f,w,h,z;if (l&1){f=b(1,1,n,l,r).o,h=t[f];w=b(1,1,n,h+1,r).u,z=t[w];}else{f=b(1,1,n,l,r).u,h=t[f];w=b(1,1,n,h+1,r).o,z=t[w];}p[++A].a=f,p[A].b=w,p[A].H=A;s B=A;if (h!=l)e[B].I(d(l,h-1));if(h+1!=z)e[B].I(d(h+1,z-1));if (z!=r)  e[B].I(d(z+1,r));K B;}s main(){scanf("%d",&n);for (i=1;i<=n;i++)scanf("%d",&a[i]),t[a[i]]=i;c(1,1,n);d(1,n);q.push(p[1]);while (!q.empty()){s x=q.top().H;q.pop();printf("%d %d ",p[x].a,p[x].b);for (i=0;i<(s)e[x].size();i++)q.push(p[e[x][i]]);}}