import qualified Data.ByteString.Char8 as B
import           Data.Char
import qualified Data.IntMap.Strict    as M
import           Data.List
import qualified Data.Sequence         as C

main :: IO ()
main = do
    n <- readLn
    as <- unfoldr (B.readInt . B.dropWhile isSpace) <$> B.getLine
    print $ solve n as

solve :: Int -> [Int] -> Int
solve n = median . count 1 . C.fromList

count :: Int -> C.Seq Int -> M.IntMap Int
count m xs
    | C.null xs = M.empty
    | even m  = M.insertWith (+) r m $ count (m + 1) rs
    | odd m   = M.insertWith (+) l m $ count (m + 1) ls
    where
        len = C.length xs
        (l C.:< ls) = C.viewl xs
        (rs C.:> r) = C.viewr xs

median :: M.IntMap Int -> Int
median mp = go 0 0 0 mp
    where
        go lsum rsum k mp
            | M.null mp    = k
            | lsum <  rsum = go (lsum + vl) rsum k  mpl
            | lsum >= rsum = go lsum (rsum + vr) kr mpr
            where
                ((_ , vl), mpl) = M.deleteFindMin mp
                ((kr, vr), mpr) = M.deleteFindMax mp
