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: from heapq import *
  import sys
  
  sys.setrecursionlimit(10**6)
  int1 = lambda x: int(x) - 1
  p2D = lambda x: print(*x, sep="\n")
  
  
  def MI():
      return map(int, sys.stdin.readline().split())
  
  
  def LI():
      return list(map(int, sys.stdin.readline().split()))
  
  
  def LLI(rows_number):
      return [LI() for _ in range(rows_number)]
  
  
  class SegtreeMin:
      def __init__(self, n):
          self.inf = 10**16
          tree_width = 1 << (n - 1).bit_length()
          self.tree_width = tree_width
          self.tree = [self.inf] * (tree_width * 2 - 1)
  
      def update(self, i, a):
          seg_i = self.tree_width - 1 + i
          self.tree[seg_i] = a
          while seg_i != 0:
              seg_i = (seg_i - 1) // 2
              self.tree[seg_i] = min(self.tree[seg_i * 2 + 1], self.tree[seg_i * 2 + 2])
  
      def refresh(self):
          for seg_i in range(self.tree_width - 2, -1, -1):
              self.tree[seg_i] = min(self.tree[seg_i * 2 + 1], self.tree[seg_i * 2 + 2])
  
      # [l,r)の最小値
      def min(self, l, r, seg_i=0, segL=0, segR=-1):
          if segR == -1:
              segR = self.tree_width
          if r <= segL or segR <= l:
              return self.inf
          if l <= segL and segR <= r:
              return self.tree[seg_i]
          segM = (segL + segR) // 2
          ret0 = self.min(l, r, seg_i * 2 + 1, segL, segM)
          ret1 = self.min(l, r, seg_i * 2 + 2, segM, segR)
          return min(ret0, ret1)
  
  
  def main():
      n = int(input())
      pp = LI()
      seg_odd = SegtreeMin(n // 2)
      seg_even = SegtreeMin(n // 2)
      ptoi = [0] + [i for i, p in sorted(enumerate(pp), key=lambda x: x[1])]
      seg_odd.tree[seg_odd.tree_width - 1 : seg_odd.tree_width - 1 + n // 2] = pp[1::2]
      seg_even.tree[seg_even.tree_width - 1 : seg_even.tree_width - 1 + n // 2] = pp[::2]
      seg_odd.refresh()
      seg_even.refresh()
      # 区間偶数番目の最小値と[l,r)をヒープに
      hp = []
      heappush(hp, [seg_even.min(0, n // 2), 0, n])
      ans = []
      for _ in range(n // 2):
          x, l, r = heappop(hp)
          if l + 2 == r:
              ans += [pp[l], pp[l + 1]]
              continue
          xi = ptoi[x]
          if l % 2:
              y = seg_even.min((xi + 1) // 2, r // 2 + 1)
          else:
              y = seg_odd.min((xi + 1) // 2, r // 2)
          yi = ptoi[y]
          if xi - l == 2:
              heappush(hp, [pp[l], l, xi])
          elif xi - l > 2:
              minp = (
                  seg_odd.min(l // 2, xi // 2)
                  if l % 2
                  else seg_even.min(l // 2, xi // 2 + 1)
              )
              heappush(hp, [minp, l, xi])
          if yi - xi - 1 == 2:
              heappush(hp, [pp[xi + 1], xi + 1, yi])
          elif yi - xi - 1 > 2:
              minp = (
                  seg_odd.min((xi + 1) // 2, yi // 2)
                  if (xi + 1) % 2
                  else seg_even.min((xi + 1) // 2, yi // 2 + 1)
              )
              heappush(hp, [minp, xi + 1, yi])
          if r - yi - 1 == 2:
              heappush(hp, [pp[yi + 1], yi + 1, r])
          elif r - yi - 1 > 2:
              minp = (
                  seg_odd.min((yi + 1) // 2, r // 2)
                  if (yi + 1) % 2
                  else seg_even.min((yi + 1) // 2, r // 2 + 1)
              )
              heappush(hp, [minp, yi + 1, r])
          ans += [x, y]
      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)"}]