import qualified Data.ByteString.Char8 as C
import qualified Data.IntSet as S
import Data.List

main = C.interact $ C.pack . show . sol . get

get = unfoldr (C.readInt . C.dropWhile (<'0'))

sol (n:xs) = f S.empty S.empty xs
  where
  f sa sb [] = g sb - g sa + 1
  f sa sb (a:b:xs) = f (S.insert a sa) (S.insert b sb) xs
  g
    | odd n     = head . drop h . S.toAscList
    | otherwise = sum . take 2 . drop (h-1) . S.toAscList
  h = n `div` 2