### BUGGY CODE ###

def main():
    n = int(input())
    p = list(map(lambda x: int(x)-1, input().split()))
    pos = [j for i, j in sorted([(j, i) for i, j in enumerate(p)])]
    basesize = n >> 1
    num = 1
    while num < basesize:
        num *= 2
    num -= 1

    tree_even = [200000]*(num*2+1)
    tree_odd = [200000]*(num*2+1)

    for i in range(num, num+basesize):
        tree_even[i] = p[(i-num)*2]
    for i in range(num-1, -1, -1):
        tree_even[i] = min(tree_even[2*i+1], tree_even[2*i+2])
    for i in range(num, num+basesize):
        tree_odd[i] = p[(i-num)*2+1]
    for i in range(num-1, -1, -1):
        tree_odd[i] = min(tree_odd[2*i+1], tree_odd[2*i+2])

    def search_even(lower, upper):
        ret = 200000
        l, r = lower+num, upper+num
        while l < r:
            if r % 2 == 0:
                r -= 1
                ret = min(ret, tree_even[r])
            if l % 2 == 0:
                ret = min(ret, tree_even[l])
                l += 1
            l >>= 1
            r >>= 1
        return ret

    def search_odd(lower, upper):
        ret = 200000
        l, r = lower+num, upper+num
        while l < r:
            if r % 2 == 0:
                r -= 1
                ret = min(ret, tree_odd[r])
            if l % 2 == 0:
                ret = min(ret, tree_odd[l])
                l += 1
            l >>= 1
            r >>= 1
        return ret

    g = dict()
    d = dict()
    q = [(0, n-1)]
    qap = q.append
    while q:
        m, M = q.pop()
        g[(m, M)] = []
        gap = g[(m, M)].append
        if m % 2 == 0:
            i1, j1 = m//2, M//2+1
            even = search_even(i1, j1)
            even_idx = pos[even]
            odd = search_odd(even_idx//2, j1)
            odd_idx = pos[odd]
            d[(m, M)] = (even+1, odd+1)
            if m != even_idx:
                qap((m, even_idx-1))
                gap((m, even_idx-1))
            if M != odd_idx:
                qap((odd_idx+1, M))
                gap((odd_idx+1, M))
            if even_idx+1 != odd_idx:
                qap((even_idx+1, odd_idx-1))
                gap((even_idx+1, odd_idx-1))
        else:
            i1, j1 = m//2, M//2
            odd = search_odd(i1, j1)
            odd_idx = pos[odd]
            even = search_even(odd_idx//2+1, j1+1)
            even_idx = pos[even]
            d[(m, M)] = (odd+1, even+1)
            if m != odd_idx:
                qap((m, odd_idx-1))
                gap((m, odd_idx-1))
            if M != even_idx:
                qap((even_idx+1, M))
                gap((even_idx+1, M))
            if odd_idx+1 != even_idx:
                qap((odd_idx+1, even_idx-1))
                gap((odd_idx+1, even_idx-1))

    import heapq
    x, y = d[(0, n-1)]
    h = [(x, y, 0, n-1)]
    heapq.heapify(h)
    ans = []

    while h:
        x, y, t1, t2 = heapq.heappop(h)
        i, j = d[(t1, t2)]
        ans += [x, y]
        for a, b in g[(t1, t2)]:
            e, f = d[(a, b)]
            heapq.heappush(h, (e, f, a, b))

    print(*ans)


main()

### FIXED CODE ###

def main():
    n = int(input())
    p = list(map(lambda x: int(x)-1, input().split()))

    pos = [j for i, j in sorted([(j, i) for i, j in enumerate(p)])]
    basesize = n >> 1
    num = 1
    while num < basesize:
        num *= 2
    num -= 1

    tree_even = [100001]*(num*2+1)
    tree_odd = [100001]*(num*2+1)

    for i in range(num, num+basesize):
        tree_even[i] = p[(i-num)*2]
    for i in range(num-1, -1, -1):
        tree_even[i] = min(tree_even[2*i+1:2*i+3])
    for i in range(num, num+basesize):
        tree_odd[i] = p[(i-num)*2+1]
    for i in range(num-1, -1, -1):
        tree_odd[i] = min(tree_odd[2*i+1:2*i+3])

    g = dict()
    d = dict()
    q = [n-1]
    qap, qp = q.append, q.pop
    while q:
        t = qp()
        m, M = t//n, t % n
        if m+1 == M:
            d[t] = p[m]*n+p[M]
            continue
        g[t] = []
        gap = g[t].append
        if m % 2 == 0:
            i1, j1 = m >> 1, (M >> 1)+1
            even = 200000
            l, r = i1+num, j1+num
            while l < r:
                if r % 2 == 0:
                    r -= 1
                    even = min(even, tree_even[r])
                if l % 2 == 0:
                    even = min(even, tree_even[l])
                    l += 1
                l >>= 1
                r >>= 1
            even_idx = pos[even]
            odd = 200000
            l, r = (even_idx >> 1)+num, j1+num
            while l < r:
                if r % 2 == 0:
                    r -= 1
                    odd = min(odd, tree_odd[r])
                if l % 2 == 0:
                    odd = min(odd, tree_odd[l])
                    l += 1
                l >>= 1
                r >>= 1
            odd_idx = pos[odd]
            d[t] = even*n+odd
            if m != even_idx:
                s = m*n+even_idx-1
                qap(s)
                gap(s)
            if M != odd_idx:
                s = (odd_idx+1)*n+M
                qap(s)
                gap(s)
            if even_idx+1 != odd_idx:
                s = (even_idx+1)*n+odd_idx-1
                qap(s)
                gap(s)
        else:
            i1, j1 = m >> 1, M >> 1
            odd = 200000
            l, r = i1+num, j1+num
            while l < r:
                if r % 2 == 0:
                    r -= 1
                    odd = min(odd, tree_odd[r])
                if l % 2 == 0:
                    odd = min(odd, tree_odd[l])
                    l += 1
                l >>= 1
                r >>= 1
            odd_idx = pos[odd]
            even = 200000
            l, r = (odd_idx >> 1)+1+num, j1+1+num
            while l < r:
                if r % 2 == 0:
                    r -= 1
                    even = min(even, tree_even[r])
                if l % 2 == 0:
                    even = min(even, tree_even[l])
                    l += 1
                l >>= 1
                r >>= 1
            even_idx = pos[even]
            d[t] = odd*n+even
            if m != odd_idx:
                s = m*n+odd_idx-1
                qap(s)
                gap(s)
            if M != even_idx:
                s = (even_idx+1)*n+M
                qap(s)
                gap(s)
            if odd_idx+1 != even_idx:
                s = (odd_idx+1)*n+even_idx-1
                qap(s)
                gap(s)

    g2 = dict()

    for i, t in g.items():
        k = d[i]
        g2[k] = []
        ga = g2[k].append
        for j in t:
            ga(d[j])

    import heapq
    h = [d[n-1]]
    heapq.heapify(h)
    ans = []
    hpop = heapq.heappop
    hpush = heapq.heappush

    while h:
        t = hpop(h)
        ans += [t//n+1, t % n+1]
        if t in g2:
            for s in g2[t]:
                hpush(h, s)

    print(*ans)


main()