{-# OPTIONS_GHC -O #-}

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

msort :: MV.STVector s Int -> MV.STVector s Int -> (Int,Int) -> STRef s Int -> ST s ()
msort xv buf (s,e) ra
  | n == 1 = return ()
  | True = do
    msort xv buf lr ra
    msort xv buf rr ra
    forM_ [s..e-1] $ \i -> MV.unsafeRead xv i >>= MV.unsafeWrite buf i
    ac <- msort2 xv buf s lr rr 0 0
    modifySTRef' ra (+ac)
  where
    n = e - s
    m = s + (n+1) `div` 2
    lr@(ls,le) = (s,m)
    rr@(rs,re) = (m,e)
--
msort2 :: MV.STVector s Int -> MV.STVector s Int -> Int -> (Int,Int) -> (Int,Int) -> Int -> Int -> ST s Int
msort2 xv buf s (ls,le) (rs,re) ra rc
  | ls==le && rs==re = return ra
  | rs==re = MV.unsafeRead buf ls >>= MV.unsafeWrite xv s >> msort2 xv buf (s+1) (ls+1,le) (rs,re) (ra+rc) rc
  | ls==le = MV.unsafeRead buf rs >>= MV.unsafeWrite xv s >> msort2 xv buf (s+1) (ls,le) (rs+1,re) ra (rc+1)
  | True = do
    l <- MV.unsafeRead buf ls
    r <- MV.unsafeRead buf rs
    if l<=r
      then MV.unsafeWrite xv s l >> msort2 xv buf (s+1) (ls+1,le) (rs,re) (ra+rc) rc
      else MV.unsafeWrite xv s r >> msort2 xv buf (s+1) (ls,le) (rs+1,re) ra (rc+1)

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

si as x = invc $ 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 = 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)