import Control.Monad.ST
import Data.Array.ST
import qualified Data.ByteString.Char8 as C
import Data.List

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

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

sol (n:xs) = f [] [] xs
  where
  f sa sb [] = g sb - g sa + 1
  f sa sb (a:b:xs) = f (a:sa) (b:sb) xs
  g s
    | odd n     = sel h s
    | otherwise = sel (h-1) s + sel h s
  h = n `div` 2

sel k xs = runST $ do 
  xa <- newListArray (0,n-1) xs :: ST s (STUArray s Int Int)
  x <- selST k xa (0,n)
  return x
  where
  n = length xs

selST k xa (a,b) = do
  m <- part xa (a,b)
  let n = m-a
  if k==n
    then readArray xa m
    else if k<n
      then selST k xa (a,m)
      else selST (k-n-1) xa (m+1,b)

part xa (a,b) = do
  x <- readArray xa a
  let loop (i,j) = if i==j
      then do {swap xa a (j-1);  return (j-1)}
      else do
        y <- readArray xa i
        if y < x 
          then loop (i+1,j)
          else do {swap xa i (j-1); loop (i,j-1)}
    in loop (a+1,b)

swap xa i j = do
  v <- readArray xa i
  w <- readArray xa j
  writeArray xa i w
  writeArray xa j v