{-
  This code was written after reading the editorial.
-}

import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import qualified Data.ByteString.Lazy.Char8 as B
import Control.Monad.Primitive
import Data.Function
import Data.List
import Data.Maybe
import Control.Monad
import Control.Monad.ST
import Data.Bits
import Debug.Trace

solve :: Int -> [Int] -> Int
solve n as = binsch 1 (10^9 + 1)
  where
    binsch xMin xMax | xMin + 1 == xMax = xMin
                     | try mid n as     = binsch mid xMax
                     | otherwise        = binsch xMin mid
      where mid = (xMax + xMin) `div` 2

try :: Int -> Int -> [Int] -> Bool
try x n as =
  t >= ((n * (n+1) `div` 2) + 1) `div` 2
  where
    t :: Int
    t = numIncr n ss
    ss :: [Int]
    ss = scanl' (+) 0 $ map (\a -> if a >= x then 1 else -1) $ as

numIncr :: Int -> [Int] -> Int
numIncr n ss = runST $ do
  v <- VUM.replicate (2*n+2) 0
  liftM sum $ forM ss $ \s -> do
    let i = s + (n+1)
    bit_add v (2*n + 1) i 1
    (+ (-1)) <$> bit_intv v i

{--
  bit_add v n i x ... a_i += x
--}
bit_add :: VUM.MVector s Int -> Int -> Int -> Int -> ST s ()
bit_add v n i x = forM_ (unfoldr f i) $ VUM.modify v (+ x)
  where f j | j > n = Nothing
            | otherwise = Just (j, j + (j .&. (-j)))

{--
  bit_intv v i    ... \Sum_{j=1}^{i} a_i
--}
bit_intv :: VUM.MVector s Int -> Int -> ST s Int
bit_intv v i = sum <$> (forM (unfoldr f i) $ VUM.read v)
  where f j | j == 0    = Nothing
            | otherwise = Just (j, j - (j .&. (-j)))


bsReadInts :: B.ByteString -> [Int]
bsReadInts = map (fst . fromJust . B.readInt) . B.words

tmain :: B.ByteString -> Int
tmain cont =
  let n : as = bsReadInts cont
  in solve n as

main = putStrLn . show . tmain =<< B.getContents
