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: # AOJ DSL_2_A "Range Minimum Query"
  # SegmantTreeの実装
  import sys
  
  input = sys.stdin.readline
  
  # 初期化最大値
  INF = (1 << 31) - 1
  
  
  class SegmentTree:
      def __init__(self, N):
          self.N = 2 ** (N - 1).bit_length()
          self.data = [[INF, -1] for _ in range(2 * self.N - 1)]
  
      # k番目の値(0-indexed)をaに変更
      def update(self, k, a):
          self.data[k + self.N - 1] = [a, k]
          k += self.N - 1
          while k > 0:
              k = (k - 1) // 2
              if self.data[2 * k + 1][0] < self.data[2 * k + 2][0]:
                  self.data[k] = self.data[2 * k + 1][:]
              else:
                  self.data[k] = self.data[2 * k + 2][:]
  
      # [l, r)の最小値取得
      # kがNodeの番号、対応する区間が[a, b)
      def query_min(self, l, r):
          L = l + self.N
          R = r + self.N
          s = [INF, -1]
          while L < R:
              if R & 1:
                  R -= 1
                  if s[0] > self.data[R - 1][0]:
                      s = self.data[R - 1]
              if L & 1:
                  if s[0] > self.data[L - 1][0]:
                      s = self.data[L - 1]
                  L += 1
              L >>= 1
              R >>= 1
          return s
  
  
  import heapq as hp
  
  N = int(input())
  A = list(map(int, input().split()))
  
  ST1 = SegmentTree(N // 2)
  ST2 = SegmentTree(N // 2)
  for i, a in enumerate(A):
      if i % 2 == 0:
          ST1.update(i // 2, a)
      else:
          ST2.update(i // 2, a)
  
  ans = []
  q = []
  v, k = ST1.query_min(0, N // 2)
  hp.heappush(q, (v, k, 0, N // 2, True))
  for _ in range(N // 2):
      valuea, ka, l, r, is1 = hp.heappop(q)
      ans.append(valuea)
      if is1:
          valueb, kb = ST2.query_min(ka, r)
          if ka < kb:
              m2, nk2 = ST2.query_min(ka, kb)
              hp.heappush(q, (m2, nk2, ka, kb + 1, False))
          if l < ka:
              m1, nk1 = ST1.query_min(l, ka)
              hp.heappush(q, (m1, nk1, l, ka, True))
          if kb + 1 < r:
              m3, nk3 = ST1.query_min(kb + 1, r)
              hp.heappush(q, (m3, nk3, kb + 1, r, True))
      else:
          valueb, kb = ST1.query_min(ka + 1, r)
          if ka + 1 < kb:
              m1, nk1 = ST1.query_min(ka + 1, kb)
              hp.heappush(q, (m1, nk1, ka + 1, kb, True))
          if l < ka:
              m2, nk2 = ST2.query_min(l, ka)
              hp.heappush(q, (m2, nk2, l, ka, False))
          if kb < r - 1:
              m3, nk3 = ST2.query_min(kb, r - 1)
              hp.heappush(q, (m3, nk3, kb, r - 1, False))
  
      ans.append(valueb)
  
  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)"}]