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: import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
  
  sys.setrecursionlimit(10**7)
  inf = 10**20
  gosa = 1.0 / 10**10
  mod = 10**9 + 7
  
  
  def LI():
      return [int(x) for x in sys.stdin.readline().split()]
  
  
  def LI_():
      return [int(x) - 1 for x in sys.stdin.readline().split()]
  
  
  def LF():
      return [float(x) for x in sys.stdin.readline().split()]
  
  
  def LS():
      return sys.stdin.readline().split()
  
  
  def I():
      return int(sys.stdin.readline())
  
  
  def F():
      return float(sys.stdin.readline())
  
  
  def S():
      return input()
  
  
  class Seg:
      def __init__(self, na, default, func):
          if isinstance(na, list):
              n = len(na)
          else:
              n = na
          i = math.ceil(math.log2(n))
          self.D = default
          self.H = i
          self.N = 2**i
          if isinstance(na, list):
              self.A = [default] * (self.N - 1) + na + [default] * (self.N - n)
              for i in range(self.N - 2, -1, -1):
                  self.A[i] = func(self.A[i * 2 + 1], self.A[i * 2 + 2])
          else:
              self.A = [default] * (self.N * 2 - 1)
          self.F = func
  
      def find(self, i):
          return self.A[i + self.N - 1]
  
      def update(self, i, x):
          i += self.N - 1
          self.A[i] = x
          while i > 0:
              i = (i - 1) // 2
              self.A[i] = self.merge(self.A[i * 2 + 1], self.A[i * 2 + 2])
  
      def merge(self, a, b):
          return self.F(a, b)
  
      def total(self):
          return self.A[0]
  
      def query(self, a, b):
          b += 1
  
          def _query(k, l, r):
              if r <= a or b <= l:
                  return self.D
              if a <= l and r <= b:
                  return self.A[k]
              m = (l + r) // 2
              vl = _query(k * 2 + 1, l, m)
              vr = _query(k * 2 + 2, m, r)
              return self.merge(vl, vr)
  
          return _query(0, 0, self.N)
  
  
  def main():
      n = I()
      a = LI()
  
      def sf(a, b):
          if a < b:
              return a
          return b
  
      s1 = Seg([c if i % 2 == 0 else inf for c, i in zip(a, range(n))], inf, sf)
      s2 = Seg([c if i % 2 == 1 else inf for c, i in zip(a, range(n))], inf, sf)
      d = {}
  
      for i in range(n):
          d[a[i]] = i
  
      def f(l, r):
          if l % 2 == 0:
              t = s1.query(l, r)
              ti = d[t]
              u = s2.query(ti + 1, r)
          else:
              t = s2.query(l, r)
              ti = d[t]
              u = s1.query(ti + 1, r)
          ui = d[u]
          nl = []
          if l < ti:
              nl.append((l, ti - 1))
          if ui - ti > 1:
              nl.append((ti + 1, ui - 1))
          if ui < r:
              nl.append((ui + 1, r))
          return ((t, u), nl)
  
      q = []
      heapq.heappush(q, f(0, n - 1))
      r = []
      while q:
          t, nl = heapq.heappop(q)
          r.append(t[0])
          r.append(t[1])
          for t, u in nl:
              heapq.heappush(q, f(t, u))
  
      return " ".join(map(str, r))
  
  
  print(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)"}]