{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE UnboxedTuples #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE ViewPatterns #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE MultiWayIf #-}

import Control.Monad
import Control.Monad.ST
import Control.Monad.State
import Control.Applicative
import Data.List
import Data.Array
import Data.Array.IO
import Data.Maybe
import Data.Bits
import Data.Ord
import Data.Ratio
import Data.Int
import Data.Char
import qualified Data.ByteString.Char8 as BS
import qualified Data.Set as Set
import Data.Tuple
import Data.Function
import Text.Printf
import Debug.Trace
import Numeric
import Control.Monad.Primitive
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as VM
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import qualified Data.Vector.Generic as VG
import qualified Data.Vector.Generic.Mutable as VGM
import qualified Data.IntMap as IM

modifyArray arr i f = readArray arr i >>= \x -> writeArray arr i (f x)

listToTuple2 [a,b] = (a,b)
listToTuple3 [a,b,c] = (a,b,c)
listToTuple4 [a,b,c,d] = (a,b,c,d)
listToTuple5 [a,b,c,d,e] = (a,b,c,d,e)

getWords = getLine >>= return . words

readIntBS = fst . fromJust . BS.readInt

for = flip map

main :: IO ()
main = do
  n <- readLn :: IO Int
  as <- map readIntBS . BS.words <$> BS.getLine :: IO [Int]

  let
    m = n*(n+1)`div`2
    solve l r
      | l == r = return l
      | l+1 == r = aux r >>= \a -> return $ if a then r else l 
      | otherwise = do
          a <- aux $ (l+r)`div`2
          if a then
            solve ((l+r)`div`2) r
            else
            solve l ((l+r)`div`2)
        where
          aux x = do
            let
              as' = scanl (+) 0 $ map (\a -> if a >= x then 1 else -1) as :: [Int]
              im = IM.fromList . (flip zip) [1..] . map head . group . sort $ as' :: IM.IntMap Int
            
            fen <- newFenwickTree (n+1) 0 (+) :: IO (IOUFenwickTree Int)
            y <- sum <$> (forM (map (im IM.!) as') $ \a -> queryFenwickTree fen a >>= \q -> modifyFenwickTree fen a (+1) >> return q)
            return $ y >= m`div`2
        

  print =<< solve (minimum as) (maximum as)


type MFenwickTree v s a = (v s a, a, (a -> a -> a), Int) -- (フェニック木, 単位元, 二項演算)
type STFenwickTree s a = MFenwickTree VM.MVector s a
type IOFenwickTree a = STFenwickTree RealWorld a
type STUFenwickTree s a = MFenwickTree VUM.MVector s a
type IOUFenwickTree a = STUFenwickTree RealWorld a

newFenwickTree :: (Applicative m, PrimMonad m, VGM.MVector v a) => Int -> a -> (a -> a -> a) -> m (MFenwickTree v (PrimState m) a)
newFenwickTree n e f = (,e,f,n) <$> VGM.replicate (n+1) e

modifyFenwickTree :: (Applicative m, PrimMonad m, VGM.MVector v a) => MFenwickTree v (PrimState m) a -> Int -> (a -> a) -> m ()
modifyFenwickTree (tree,e,f,size) i g = do
  aux i
  where
    aux j = do
      when (j <= size) $ do
        VGM.write tree j =<< g <$> VGM.read tree j
        aux (j + (j .&. (-j)))

queryFenwickTree :: (Applicative m, PrimMonad m, VGM.MVector v a) => MFenwickTree v (PrimState m) a -> Int -> m a
queryFenwickTree (tree,e,f,size) i = do
  aux i
  where
    aux j
      | j <= 0 = return e
      | otherwise = f <$> VGM.read tree j <*> aux (j - (j .&. (-j)))

lowerBoundFenwickTree :: (Num a, Ord a, Eq a, Applicative m, PrimMonad m, VGM.MVector v a) => MFenwickTree v (PrimState m) a -> a -> m Int
lowerBoundFenwickTree (tree,e,f,size) x = do
  aux k 0 x
  where
    k = (2 ^ (floor $ logBase 2 (fromIntegral size)))
    aux i j w
      | i == 0 = return (j+1)
      | otherwise = do
          if i+j <= size then do
            a <- VGM.read tree (i+j)
            if a < w then aux (i `div` 2) (i+j) (w-a) else aux (i `div` 2) j w
            else
            aux (i `div` 2) j w


