{-# OPTIONS_GHC -O #-}

import Data.List (scanl, unfoldr)
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

msort :: MV.STVector s Int -> (Int,Int) -> STRef s Int -> ST s ()
msort xv (s,e) ra
  | n == 1 = return ()
  | True = do
    msort xv lr ra
    msort xv rr ra
    tv <- V.freeze xv
    rc <- newSTRef 0
    msort2 xv tv s lr rr ra rc
  where
    n = e - s
    m = s + n `div` 2
    lr@(ls,le) = (s,m)
    rr@(rs,re) = (m,e)
--
msort2 :: MV.STVector s Int -> (V.Vector Int) -> Int -> (Int,Int) -> (Int,Int) -> STRef s Int -> STRef s Int -> ST s ()
msort2 xv tv s (ls,le) (rs,re) ra rc
  | ls==le && rs==re = return ()
  | rs==re = forM_ [ls..le-1] $ \i -> (MV.unsafeWrite xv (s+i-ls) (tv V.! i) >> liftM2 (+) (readSTRef ra) (readSTRef rc) >>= writeSTRef ra)
  | ls==le = forM_ [rs..re-1] $ \i -> (MV.unsafeWrite xv (s+i-rs) (tv V.! i) >> liftM (+1) (readSTRef rc) >>= writeSTRef rc)
  | l <= r = liftM2 (+) (readSTRef ra) (readSTRef rc) >>= writeSTRef ra >> MV.unsafeWrite xv s l >> msort2 xv tv (s+1) (ls+1,le) (rs,re) ra rc
  | True   = liftM (+1) (readSTRef rc) >>= writeSTRef rc >> MV.unsafeWrite xv s r >> msort2 xv tv (s+1) (ls,le) (rs+1,re) ra rc
    where
      l = tv V.! ls
      r = tv V.! rs

invc ss = runST $ do
  v <- V.thaw $ V.fromList ss :: ST s (MV.STVector s Int)
  ra <- newSTRef 0
  msort v (0, MV.length v) ra
  readSTRef ra

si as x = invc ss
  where
    ss = tail $ 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 = iv >= (tn+1) `div` 2
  where
    iv = (-) tn $ si as $ av V.! x

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