import Data.Monoid
import Data.Maybe
import qualified Data.ByteString.Char8 as B

readInt :: B.ByteString -> Int
readInt = maybe undefined fst . B.readInt

readInts :: B.ByteString -> [Int]
readInts = map readInt . B.words

main = do
  n <- readLn :: IO Int
  ps <- readInts <$> B.getLine
  putStrLn $ unwords $ map show (maids n ps)

maids n ps = go n treeEven treeOdd q
  where
    q = singleton (val treeEven, (1, n), False) :: SkewBinomialHeap (V, (Int, Int), Bool)
    treeEven = fromList n $ zipWith (\i p -> V p i) [1..] $ zipWith ($) (cycle [id, const maxBound]) ps
    treeOdd  = fromList n $ zipWith (\i p -> V p i) [1..] $ zipWith ($) (cycle [const maxBound, id]) ps

go n treeEven treeOdd q
  | isEmpty q = []
  | otherwise = pemin : pomin : go n treeEven treeOdd q2
  where
    ((V pemin i, (si,sj), flag), q1) = deleteFindMin q
    (V pomin j) = query n (if flag then treeEven else treeOdd) (i+1) sj
    seg1 = if si == i then Nothing else Just (query n (if not flag then treeEven else treeOdd) si (i-1), (si, i-1), flag)
    seg2 = if succ i == j then Nothing else
             Just (query n (if flag then treeEven else treeOdd) (i+1) (j-1), (i+1, j-1), not flag)
    seg3 = if j == sj then Nothing else Just (query n (if not flag then treeEven else treeOdd) (j+1) sj, (j+1, sj), flag)
    q2 = foldr insert q1 (catMaybes [seg1, seg2, seg3])


data V = V !Int !Index deriving (Eq, Ord, Show)

instance Monoid V where
  mempty = V maxBound undefined
  mappend v1@(V p1 _) v2@(V p2 _) = if p1 < p2 then v1 else v2

data SegTree m =
  Leaf !m |
  Node !m !(SegTree m) !(SegTree m)
  deriving (Eq, Show)

type Index = Int
type Size = Int

val :: Monoid m => SegTree m -> m
val (Leaf v) = v
val (Node v _ _) = v

fromList :: Monoid m => Size -> [m] -> SegTree m
fromList 1 [x] = Leaf x
fromList n xs = Node (val left <> val right) left right
  where
    m = div n 2
    (xs1, xs2) = splitAt m xs
    left = fromList m xs1
    right = fromList (n - m) xs2

query :: Monoid m => Size -> SegTree m -> Index -> Index -> m
query 1 (Leaf v) 1 1 = v
query _ (Leaf _) _ _ = undefined
query n (Node v l r) i j
  | (i, j) == (1, n) = v
  | j <= m = query m l i j
  | i > m = query (n - m) r (i - m) (j - m)
  | otherwise = query m l i m <> query (n - m) r 1 (j - m)
  where
    m = div n 2


class Heap h where
  empty :: Ord a => h a
  isEmpty :: Ord a => h a -> Bool
  singleton :: Ord a => a -> h a

  insert :: Ord a => a -> h a -> h a
  merge :: Ord a => h a -> h a -> h a

  findMin :: Ord a => h a -> a
  deleteMin :: Ord a => h a -> h a
  deleteFindMin :: Ord a => h a -> (a, h a)

data Tree a = HNode Int a [a] [Tree a]

newtype SkewBinomialHeap a = SBH [Tree a]

rank :: Tree a -> Int
rank (HNode r _ _ _) = r

root :: Tree a -> a
root (HNode _ x _ _) = x

link :: Ord a => Tree a -> Tree a -> Tree a
link t1@(HNode r x1 xs1 c1) t2@(HNode _ x2 xs2 c2)
  | x1 <= x2 = HNode (r + 1) x1 xs1 (t2 : c1)
  | otherwise = HNode (r + 1) x2 xs2 (t1 : c2)

skewLink :: Ord a => a -> Tree a -> Tree a -> Tree a
skewLink x t1 t2
  | x <= y = HNode r x (y : ys) c
  | otherwise = HNode r y (x : ys) c
  where
    HNode r y ys c = link t1 t2

insTree :: Ord a => Tree a -> [Tree a] -> [Tree a]
insTree t [] = [t]
insTree t ts@(t' : ts')
  | rank t < rank t' = t : ts
  | otherwise = insTree (link t t') ts'

mrg :: Ord a => [Tree a] -> [Tree a] -> [Tree a]
mrg ts1 [] = ts1
mrg [] ts2 = ts2
mrg ts1@(t1 : ts1') ts2@(t2 : ts2')
  | rank t1 < rank t2 = t1 : mrg ts1' ts2
  | rank t2 < rank t1 = t2 : mrg ts1 ts2'
  | otherwise = insTree (link t1 t2) (mrg ts1' ts2')

normalize :: Ord a => [Tree a] -> [Tree a]
normalize [] = []
normalize (t : ts) = insTree t ts

removeMinTree :: Ord a => [Tree a] -> (Tree a, [Tree a])
removeMinTree [] = error "empty heap"
removeMinTree [t] = (t, [])
removeMinTree (t : ts)
  | root t < root t' = (t, ts)
  | otherwise = (t', t : ts')
  where
    (t', ts') = removeMinTree ts

instance Heap SkewBinomialHeap where
  empty = SBH []
  isEmpty (SBH ts) = null ts
  singleton x = insert x empty

  insert x (SBH (t1 : t2 : ts))
    | rank t1 == rank t2 = SBH (skewLink x t1 t2 : ts)
  insert x (SBH ts) = SBH (HNode 0 x [] [] : ts)

  merge (SBH ts1) (SBH ts2) = SBH (mrg (normalize ts1) (normalize ts2))

  findMin (SBH ts) = root t
    where
      (t, _) = removeMinTree ts

  deleteMin (SBH ts) = foldr insert (SBH ts') xs
    where
      (HNode _ _ xs ts1, ts2) = removeMinTree ts
      ts' = mrg (reverse ts1) (normalize ts2)

  deleteFindMin (SBH ts) = (root t, foldr insert (SBH ts') xs)
    where
      (t, _) = removeMinTree ts
      (HNode _ _ xs ts1, ts2) = removeMinTree ts
      ts' = mrg (reverse ts1) (normalize ts2)

Measured memory_bytes: 95868