{-# OPTIONS_GHC -O2 -funbox-strict-fields #-}
{-# LANGUAGE BangPatterns      #-}
{-# LANGUAGE CPP               #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE TupleSections     #-}

import           Control.Applicative
import           Control.Monad
import           Control.Monad.Primitive
import           Control.Monad.ST
import           Control.Monad.State.Strict
import           Data.Bool
import qualified Data.ByteString.Char8       as B
import qualified Data.ByteString.Unsafe      as B
import           Data.Char
import           Data.Function
import qualified Data.IntMap.Strict          as IM
import qualified Data.IntSet                 as IS
import           Data.List
import qualified Data.Map.Strict             as M
import           Data.Monoid
import           Data.Ord
import           Data.Primitive.MutVar
import qualified Data.Set                    as S
import           Data.Tuple
import qualified Data.Vector                 as V
import qualified Data.Vector.Generic         as G
import qualified Data.Vector.Generic.Mutable as GM
import qualified Data.Vector.Unboxed         as U
import qualified Data.Vector.Unboxed.Mutable as UM
import           Debug.Trace
import           Foreign                     hiding (void)
import           Unsafe.Coerce

main :: IO ()
main = do
    !n <- readLn :: IO Int
    xs <- U.toList.U.unfoldrN n (B.readInt.B.dropWhile isSpace) <$> B.getLine
    putStrLn.unwords.map show $ solve xs

solve xs = concatMap(\(x,y)->[x,y]) $ go xs
  where
    go [] = []
    go [x, y] = [(x, y)]
    go (x:y:xs) = (l, r) : min3 (go ls) (go ms) (go rs)
      where
        (ls, l, ms, r, rs) = split [] x [] y [] xs

    split ls !l ms !r rs [] = (reverse ls, l, reverse ms, r, reverse rs)
    split ls !l ms !r rs (x:y:xs)
      | x < l = split (rs ++ r:ms ++ l:ls) x [] y [] xs
      | y < r = split ls l (x:rs++r:ms) y [] xs
      | otherwise = split ls l ms r (y:x:rs) xs

    min3 (x:xs) (y:ys) (z:zs)
      | x < y, x < z = x : min3 xs (y:ys) (z:zs)
      | y < z, y < x = y : min3 (x:xs) ys (z:zs)
      | otherwise = z : min3 (x:xs) (y:ys) zs
    min3 (x:xs) (y:ys) [] = min2 (x:xs) (y:ys)
    min3 (x:xs) [] (z:zs) = min2 (x:xs) (z:zs)
    min3 [] (y:ys) (z:zs) = min2 (y:ys) (z:zs)
    min3 xs [] [] = xs
    min3 [] ys [] = ys
    min3 [] [] zs = zs

    min2 (x:xs) (y:ys)
      | x < y = x : min2 xs (y:ys)
      | otherwise = y : min2 (x:xs) ys
    min2 xs [] = xs
    min2 [] ys = ys
