output_description: Print the lexicographically smallest permutation, with spaces in between.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      p_1 p_2 ... p_N
attempt: 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)])]
  
      class segtree:
          def __init__(self, base, monoid, ini):  # self,モノイド,元の配列
              # ini：上限（下限）,base：元の配列,monoid：モノイド,tree：セグ木,depth：treeの深さ,
              # basesize：baseの要素数,treesize：treeの要素数,num：treesize-basesize
              # 初期値（上限とか下限）を決定
              self.ini = ini
              # セグ木の要素数（num）および深さ（depth）を計算
              self.basesize = len(base)
              num, depth, basesize = 1, 1, self.basesize
              while num < basesize:
                  num *= 2
                  depth += 1
              num -= 1
              self.num, self.depth = num, depth
              # 関数（モノイド、今回はmin）を設定
              self.monoid = monoid
              # セグ木を構築
              self.treesize = num * 2 + 1
              self.tree = [None] * self.treesize
              tree = self.tree
              # segtree[m]以降に代入したい配列を入力していく
              for i in range(num, num + basesize):
                  tree[i] = base[i - num]
              for i in range(num + basesize, self.treesize):
                  tree[i] = ini
              # segtree[m]以降の情報を使って、0に向かってセグ木を構築していく
              for i in range(num - 1, -1, -1):
                  tree[i] = monoid(tree[2 * i + 1], tree[2 * i + 2])
  
          # 半開区間[lower,upper)の最小値（とか）を探す関数
          def search(self, lower, upper):
              # 返り値を初期化
              ret, num = self.ini, self.num
              l, r, monoid, tree = lower + num, upper + num, self.monoid, self.tree
              while l < r:
                  if r % 2 == 0:
                      r -= 1
                      ret = monoid(ret, tree[r])
                  if l % 2 == 0:
                      ret = monoid(ret, tree[l])
                      l += 1
                  l //= 2
                  r //= 2
              return ret
  
      seg_even = segtree(p[::2], min, n + 1)
      seg_odd = segtree(p[1::2], min, n + 1)
  
      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 = seg_even.search(i1, j1)
              odd = seg_odd.search(i1, j1)
              even_idx, odd_idx = pos[even], 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 = seg_odd.search(i1, j1)
              even = seg_even.search(i1 + 1, j1 + 1)
              even_idx, odd_idx = pos[even], pos[odd]
              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()
  
problem_description: Statement
  
  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.
samples: [{"input": "4\n    3 2 4 1", "output": "3 1 2 4\n    \n\nThe solution above is obtained as follows:\n\np | q  \n---|---  \n(3, 2, 4, 1) | ()  \n\u2193 | \u2193  \n(3, 1) | (2, 4)  \n\u2193 | \u2193  \n() | (3, 1, 2, 4)  \n  \n* * *"}, {"input": "2\n    1 2", "output": "1 2\n    \n\n* * *"}, {"input": "8\n    4 6 3 2 8 5 7 1", "output": "3 1 2 7 4 6 8 5\n    \n\nThe solution above is obtained as follows:\n\np | q  \n---|---  \n(4, 6, 3, 2, 8, 5, 7, 1) | ()  \n\u2193 | \u2193  \n(4, 6, 3, 2, 7, 1) | (8, 5)  \n\u2193 | \u2193  \n(3, 2, 7, 1) | (4, 6, 8, 5)  \n\u2193 | \u2193  \n(3, 1) | (2, 7, 4, 6, 8, 5)  \n\u2193 | \u2193  \n() | (3, 1, 2, 7, 4, 6, 8, 5)"}]