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

import Prelude hiding (length)
import Data.List (scanl, unfoldr)
import qualified Data.ByteString.Char8 as B
import qualified Data.Vector.Unboxed as V
import qualified Data.IntSet as S

import Control.Monad                        (forM_)
import Control.Monad.ST            as ST
import Data.Functor                         ((<$>))
import Data.STRef                  as STRef
import Data.Vector.Unboxed.Mutable
    (length, unsafeSlice, unsafeWrite, unsafeRead, new, STVector)

countInversions :: [Int] -> Int
countInversions xs' = runST $ do
    count   <- newSTRef (0 :: Int)
    xs      <- V.thaw $ V.fromList xs'
    let len =  length xs
    buf     <- new len

    let chunkSizes = takeWhile (< len) $ iterate (* 2) 1
    forM_ chunkSizes $ \chunkSize -> 
        forM_ [0, chunkSize * 2 .. len - chunkSize - 1] $ \i -> do
            let low    =   i
            let mid    =   i + chunkSize
            let high   =  (i + chunkSize * 2) `min` len
            let left   =  unsafeSlice low (mid  - low) xs
            let right  =  unsafeSlice mid (high - mid) xs
            deltaCount <- merge left right buf 0 0 0 0
            modifySTRef' count (+deltaCount)
    
    readSTRef count

 where
    merge :: STVector s Int -> STVector s Int -> STVector s Int -> Int -> Int -> Int -> Int -> ST s Int
    merge a0@(length -> l0) a1@(length -> l1) buf i0 i1 i !count
    {- Merge a0[i0 .. $] and a1[i1 .. $] into buf[i .. $],
        finally write the contents of buf back to a0 and a1. -}
     | i0 == l0 && i1 == l1 = do
        forM_ [0 .. l0 - 1] $ \j  ->
            unsafeWrite a0 j  =<< unsafeRead buf j
        forM_ [0 .. l1 - 1] $ \j' -> 
            unsafeWrite a1 j' =<< unsafeRead buf (j' + l0)
        return count

     | i0 == l0 = do
        unsafeWrite buf i =<< unsafeRead a1 i1
        merge a0 a1 buf i0 (i1 + 1) (i + 1) count

     | i1 == l1 = do
        unsafeWrite buf i =<< unsafeRead a0 i0
        merge a0 a1 buf (i0 + 1) i1 (i + 1) count

     | otherwise = do
        x0 <- unsafeRead a0 i0
        x1 <- unsafeRead a1 i1
        case compare x0 x1 of
         o | o==LT || o==EQ -> do
            unsafeWrite buf i =<< unsafeRead a0 i0
            merge a0 a1 buf (i0 + 1) i1 (i + 1) count
         _  -> do
            unsafeWrite buf i =<< unsafeRead a1 i1
            merge a0 a1 buf i0 (i1 + 1) (i + 1) (count + l0 - i0)

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