-- Try AtCoder
-- author: Leonardone @ NEETSDKASU

import Data.List (sort)

main = getContents >>= print . solve . map read . words

solve (n:a) = ans where
    f (i, os, es) v = if even i then (i - 1, os, v : es) else (i - 1, v : os, es)
    (_, os, es) = foldl f (n, [], []) a
    g xs []     []     = reverse xs
    g xs (o:os) []     = g (o:xs)   os []
    g xs (o:os) (e:es) = g (e:o:xs) os es
    (oss, ess) = fmap sort (os, es)
    bs = g [] oss ess
    h c d []     es     = if d then h c False (reverse es) [] else c
    h c d (x:xs) []     = h c d xs [x]
    h c d (x:xs) (e:es) =
        if e > x then
            h (c + 1) (d || True) xs (e:x:es)
        else
            h c d xs (x:e:es)
    ans = h 0 False bs []