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.buffer.readline

# O(NlogN)構築、クエリO(1)のRMQ
# 変更はできない
class SparseTable():
    def __init__(self, N, A):
        self.N = N
        self.logN = N.bit_length()
        self.A = A
        self.table = [[i for i in range(N)]]
        for k in range(self.logN):
            tab = []
            for i in range(self.N-(1<<(k+1))+1):
                ind1 = self.table[-1][i]
                ind2 = self.table[-1][i+(1<<k)]
                if self.A[ind1] <= self.A[ind2]:
                    tab.append(ind1)
                else:
                    tab.append(ind2)
            self.table.append(tab)
    
    # [l, r)のminの(val, key)
    def query_min(self, l, r):
        k = (r-l).bit_length()-1
        indl = self.table[k][l]
        indr = self.table[k][r-(1<<k)]
        if self.A[indl] <= self.A[indr]:
            return self.A[indl], indl
        return self.A[indr], indr

import heapq as hp
N = int(input())
A = list(map(int, input().split()))

def main():
    SP1 = SparseTable((N+1)//2, A[::2])
    SP2 = SparseTable(N//2, A[1::2])

    ans = []
    q = []
    v, k = SP1.query_min(0, N//2)
    dic = {}
    dic[v] = (k, 0, N//2, True)
    hp.heappush(q, v)
    for _ in range(N//2):
        valuea = hp.heappop(q)
        ka, l, r, is1 = dic[valuea]
        ans.append(str(valuea))
        if is1:
            valueb, kb = SP2.query_min(ka, r)
            if ka < kb:
                m2, nk2 = SP2.query_min(ka, kb)
                hp.heappush(q, m2)
                dic[m2] = (nk2, ka, kb+1, False)
            if l < ka:
                m1, nk1 = SP1.query_min(l, ka)
                hp.heappush(q, m1)
                dic[m1] = (nk1, l, ka, True)
            if kb+1 < r:
                m3, nk3 = SP1.query_min(kb+1, r)
                hp.heappush(q, m3)
                dic[m3] = (nk3, kb+1, r, True)
        else:
            valueb, kb = SP1.query_min(ka+1, r)
            if ka+1 < kb:
                m1, nk1 = SP1.query_min(ka+1, kb)
                hp.heappush(q, m1)
                dic[m1] = (nk1, ka+1, kb, True)
            if l < ka:
                m2, nk2 = SP2.query_min(l, ka)
                hp.heappush(q, m2)
                dic[m2] = (nk2, l, ka+1, False)
            if kb < r-1:
                m3, nk3 = SP2.query_min(kb, r-1)
                hp.heappush(q, m3)
                dic[m3] = (nk3, kb, r, False)

        ans.append(str(valueb))

    print(" ".join(ans))


if __name__ == "__main__":
    main()