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 PYTHON3):

Solution:
import sys
input = sys.stdin.readline
from heapq import heappush, heappop

N = int(input())
A = [int(x) for x in input().split()]
a_to_i = {a:i for i,a in enumerate(A)}

# sparse table を使ってRMQ
# parityの同じところだけを見るようにしておく

U = len(A).bit_length()
sp = [None,A]
for i in range(2,U):
    L = 1 << (i-1)
    sp.append([x if x < y else y for x,y in zip(sp[-1][:-L], sp[-1][L:])])

def RMQ(x,y):
    # x番目から偶数番目だけ見て[x,y]での最小値を返す
    d = y - x
    if d <= 1:
        return A[x]
    n = d.bit_length()
    arr = sp[n-1]
    ax = arr[x]
    ay = arr[y+2-(1<<(n-1))]
    return ax if ax < ay else ay

def F(x,y):
    # 辞書式で最小の2つ組をとる
    # そのあと、今後調べないといけない区間の一覧を返す
    x1 = RMQ(x,y-1)
    i1 = a_to_i[x1]
    x2 = RMQ(i1+1,y)
    i2 = a_to_i[x2]
    task = ((x,y) for x,y in ((x,i1-1), (i1+1,i2-1), (i2+1,y)) if y > x)
    return x1,x2,task

q = [(None,None,((0,N-1),))]
answer = []
while q:
    x,y,task = heappop(q)
    answer.append(x)
    answer.append(y)
    for left,right in task:
        heappush(q,F(left,right))

print(' '.join(map(str,answer[2:])))