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:
def main():
    import sys
    from heapq import heappush, heappop
    input = sys.stdin.buffer.readline

    # min
    def STfunc(a, b):
        if a < b:
            return a
        else:
            return b

    # クエリは0-indexedで[l, r)
    class SparseTable():
        def __init__(self, A):
            # A: 処理したい数列
            self.N = len(A)
            self.K = self.N.bit_length() - 1
            self.table = [[0] * (self.K + 1) for _ in range(self.N)]
            for i, a in enumerate(A):
                self.table[i][0] = A[i]
            for k in range(1, self.K + 1):
                for i in range(self.N):
                    j = i + (1 << (k - 1))
                    if j <= self.N - 1:
                        self.table[i][k] = STfunc(self.table[i][k - 1], self.table[j][k - 1])
                    else:
                        self.table[i][k] = self.table[i][k - 1]

        def query(self, l, r):
            # [l, r)の最小値を求める
            k = (r - l).bit_length() - 1
            return STfunc(self.table[l][k], self.table[r - (1 << k)][k])

    N = int(input())
    n = N//2
    A = list(map(int, input().split()))

    A_even = A[0:N:2]
    A_odd = A[1:N:2]
    ST_even = SparseTable(A_even)
    ST_odd = SparseTable(A_odd)
    val2idx = [0] * (N+1)
    for i in range(N):
        val2idx[A[i]] = i

    ans = []
    ans_append = ans.append
    pq = [(ST_even.query(0, n), 0, N)]
    for t in range(n):
        v1, left, right = heappop(pq)
        ans_append(v1)
        i = val2idx[v1]
        if i & 1:
            v2 = ST_even.query((i+1)//2, right//2 + 1)
            ans_append(v2)
            j = val2idx[v2]
            if left != i:
                heappush(pq, (ST_odd.query(left//2, i//2), left, i))
            if j-i > 1:
                heappush(pq, (ST_even.query((i+1)//2, j//2), i+1, j))
            if j+1 != right:
                heappush(pq, (ST_odd.query((j+1)//2, right//2), j+1, right))
        else:
            v2 = ST_odd.query(i//2, right//2)
            ans_append(v2)
            j = val2idx[v2]
            if left != i:
                heappush(pq, (ST_even.query(left//2, i//2), left, i))
            if j-i > 1:
                heappush(pq, (ST_odd.query((i+1)//2, j//2), i+1, j))
            if j+1 != right:
                heappush(pq, (ST_even.query((j+1)//2, right//2), j+1, right))

    print(*ans)


if __name__ == '__main__':
    main()