{-# OPTIONS_GHC -O #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE ViewPatterns #-}

import Data.List (scanl, unfoldr, foldl')
import qualified Data.ByteString.Char8 as B
import qualified Data.IntSet as S

import Control.Monad
import Control.Monad.ST
import Data.STRef
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as MV

cntInv :: [Int] -> Int
cntInv xs' = runST $ do
  cnt <- newSTRef 0 :: ST s (STRef s Int)
  xs  <- V.unsafeThaw $ V.fromList xs' :: ST s (MV.STVector s Int)
  len <- pure $ MV.length xs
  buf <- MV.new len :: ST s (MV.STVector s Int)
  --
  forM_ [(cs,ix)|cs<-takeWhile(<len)$iterate(*2)1, ix<-[0,cs*2..len-cs-1]] $ \(cs,ix) -> do
    lbuf <- pure $ MV.unsafeSlice ix cs xs
    rbuf <- pure $ MV.unsafeSlice (ix+cs) ((min len (ix+cs*2))-(ix+cs)) xs
    dc <- merge lbuf rbuf buf 0 0 0 0
    modifySTRef' cnt (+dc)
  --
  readSTRef cnt
  --
  where
    merge :: MV.STVector s Int -> MV.STVector s Int -> MV.STVector s Int -> Int ->Int -> Int -> Int -> ST s Int
    merge lbuf@(MV.length->llen) rbuf@(MV.length->rlen) buf ixl ixr ix !cnt
      | ixl == llen && ixr == rlen = do
        forM_ [0..llen-1] $ \i -> MV.unsafeRead buf i >>= MV.unsafeWrite lbuf i
        forM_ [0..rlen-1] $ \i -> MV.unsafeRead buf (llen+i) >>= MV.unsafeWrite rbuf i
        return cnt
      --
      | ixl == llen = MV.unsafeRead rbuf ixr >>= MV.unsafeWrite buf ix >> merge lbuf rbuf buf ixl (ixr+1) (ix+1) cnt
      --
      | ixr == rlen = MV.unsafeRead lbuf ixl >>= MV.unsafeWrite buf ix >> merge lbuf rbuf buf (ixl+1) ixr (ix+1) cnt
      --
      | True = do
        lv <- MV.unsafeRead lbuf ixl
        rv <- MV.unsafeRead rbuf ixr
        if lv<=rv
          then MV.unsafeWrite buf ix lv >> merge lbuf rbuf buf (ixl+1) ixr (ix+1) cnt
          else MV.unsafeWrite buf ix rv >> merge lbuf rbuf buf ixl (ixr+1) (ix+1) (cnt+llen-ixl)

si as x = cntInv $ scanl (\ac a->if a>=x then ac+1 else ac-1) 0 as

bsearch f (a,b)
  | a+1 == b = a
  | f m  = bsearch f (m,b)
  | True = bsearch f (a,m)
  where m = (a + (b-a)`div`2)

ff av as tn x = niv >= (tn+1)`div`2
  where
    niv = (-) tn $ si as $ av V.! x

main=do
  n<-readLn::IO Int
  !as<-unfoldr (B.readInt.B.dropWhile(==' '))<$>B.getLine::IO[Int]
  let !av = V.fromList $ S.toAscList $ S.fromList as
  let !tn = (n*(n+1))`div`2
  print $ (V.!) av $ bsearch (ff av as tn) (-1,V.length av)