{-# 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.unfoldrN n (B.readInt.B.dropWhile isSpace) <$> B.getLine
    putStrLn.unwords.map show $ solve xs

solve :: U.Vector Int -> [Int]
solve xs = concatMap(\(x,y)->[x,y]) $ go 0 (U.length xs-1)
  where
    !rmq0 = buildRMQ.U.map(\(i,x) -> (if even i then x else maxBound))$ U.indexed xs
    !rmq1 = buildRMQ.U.map(\(i,x) -> (if odd i then x else maxBound))$ U.indexed xs
    go l0 r0
      | l0 >= r0 = []
      | r0 - l0 == 1 = [(U.unsafeIndex xs l0, U.unsafeIndex xs r0)]
      | otherwise = let  (l, r) = split (even l0) l0 r0
                    in (U.unsafeIndex xs l, U.unsafeIndex xs r) : min3 (go l0 (l-1)) (go (l+1) (r-1)) (go (r+1) r0)

    split True l0 r0 = (l, r)
      where
        l = queryMinIndex rmq0 l0 r0
        r = queryMinIndex rmq1 l r0
    split False l0 r0 = (l, r)
      where
        l = queryMinIndex rmq1 l0 r0
        r = queryMinIndex rmq0 l r0

    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
-------------------------------------------------------------------------------
newtype RMQ a = RMQ {rmqTable :: V.Vector (U.Vector (a, Int))}

buildRMQ :: (U.Unbox a, Ord a) => U.Vector a -> RMQ a
buildRMQ vec = RMQ
    . V.scanl' (\acc i -> U.zipWith min acc $ U.drop i acc) veci
    $ V.iterateN (floorLog2 $ U.length vec) (*2) 1
  where
    veci = U.map swap $ U.indexed vec

queryMin :: (U.Unbox a, Ord a) => RMQ a -> Int -> Int -> a
queryMin rmq l r
    | l == r = fst $ unsafeIndex2 (rmqTable rmq) 0 l
    | l < r = fst $ min x y
    | otherwise = error "queryMin"
  where
    lg = floorLog2 $ r - l
    x = unsafeIndex2 (rmqTable rmq) lg l
    y = unsafeIndex2 (rmqTable rmq) lg $ r - unsafeShiftL 1 lg + 1
{-# INLINE queryMin #-}

queryMinIndex :: (U.Unbox a, Ord a) => RMQ a -> Int -> Int -> Int
queryMinIndex rmq l r
    | l < r = snd $ min x y
    | l == r = snd $ unsafeIndex2 (rmqTable rmq) 0 l
    | otherwise = error "queryMinIndex"
  where
    lg = floorLog2 $ r - l
    x = unsafeIndex2 (rmqTable rmq) lg l
    y = unsafeIndex2 (rmqTable rmq) lg $ r - unsafeShiftL 1 lg + 1
{-# INLINE queryMinIndex #-}

unsafeIndex2 :: (G.Vector u a, G.Vector v (u a))
             => v (u a) -> Int -> Int -> a
unsafeIndex2 vv i = G.unsafeIndex (G.unsafeIndex vv i)
{-# INLINE unsafeIndex2 #-}

floorLog2 :: Int -> Int
floorLog2 x = fromIntegral $ unsafeShiftR y 52 - 1023
  where
    y :: Word64
    y = unsafeCoerce (fromIntegral x :: Double)




Measured memory_bytes: 186876