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: class segment_tree:
      def __init__(self, N, operator_M, e_M):
          self.op_M = operator_M
          self.e_M = e_M
  
          self.N0 = 1 << (N - 1).bit_length()
          self.dat = [self.e_M] * (2 * self.N0)
  
      # 長さNの配列 initial で初期化
      def build(self, initial):
          self.dat[self.N0 : self.N0 + len(initial)] = initial[:]
          for k in range(self.N0 - 1, 0, -1):
              self.dat[k] = self.op_M(self.dat[2 * k], self.dat[2 * k + 1])
  
      # a_k の値を x に更新
      def update(self, k, x):
          k += self.N0
          self.dat[k] = x
          k //= 2
          while k:
              self.dat[k] = self.op_M(self.dat[2 * k], self.dat[2 * k + 1])
              k //= 2
  
      # 区間[L,R]をopでまとめる
      def query(self, L, R):
          L += self.N0
          R += self.N0 + 1
          sl = sr = self.e_M
          while L < R:
              if R & 1:
                  R -= 1
                  sr = self.op_M(self.dat[R], sr)
              if L & 1:
                  sl = self.op_M(sl, self.dat[L])
                  L += 1
              L >>= 1
              R >>= 1
          return self.op_M(sl, sr)
  
      def get(self, k):  # k番目の値を取得。query[k,k]と同じ
          return self.dat[k + self.N0]
  
  
  # coding: utf-8
  # Your code here!
  import sys
  
  read = sys.stdin.read
  readline = sys.stdin.readline
  
  n, *p = map(int, read().split())
  
  INF = 1 << 30
  p += [INF, INF]
  
  
  def argmin(i, j):
      if p[i] < p[j]:
          return i
      else:
          return j
  
  
  even = segment_tree(n // 2 + 1, argmin, n)
  odd = segment_tree(n // 2 + 1, argmin, n + 1)
  
  # print(p[::2],n//2)
  even.build(range(0, n + 2, 2))
  odd.build(range(1, n + 2, 2))
  
  # print(p)
  # print(even.dat)
  # print(odd.dat)
  
  
  def merge(a, b):
      la, lb = len(a), len(b)
      res = [0] * (la + lb)
      ia = ib = 0
      for i in range(la + lb):
          if ib == lb:
              res[i:] = a[ia:]
              return res
          if ia == la:
              res[i:] = b[ib:]
              return res
          if a[ia] < b[ib]:
              res[i] = a[ia]
              ia += 1
          else:
              res[i] = b[ib]
              ib += 1
      return res
  
  
  def merge3(l0, l1, l2):
      if len(l0) < len(l1):
          if len(l1) < len(l2):
              return merge(merge(l0, l1), l2)
          else:
              return merge(merge(l0, l2), l1)
      else:
          if len(l0) < len(l2):
              return merge(merge(l0, l1), l2)
          else:
              return merge(merge(l1, l2), l0)
  
  
  def f(i, j):
      if i >= j:
          return []
      if i + 1 == j:
          return [(p[i], p[j])]
  
      k = odd.query(i // 2, (j - 1) // 2) if i % 2 else even.query(i // 2, (j - 1) // 2)
      l = even.query((k + 1) // 2, j // 2) if i % 2 else odd.query((k + 1) // 2, j // 2)
      res = [(p[k], p[l])] + merge3(f(i, k - 1), f(k + 1, l - 1), f(l + 1, j))
  
      # print(f"i={i},j={j},k={k},l={l},{res}")
  
      return res
  
  
  # print(p)
  r = f(0, n - 1)
  
  ans = []
  for lst in r:
      ans += [lst[0], lst[1]]
  
  print(*ans)
  
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)"}]