main :: IO ()
main = do
    _  <- getLine
    xs <- fmap read . words <$> getLine
    answer $ solve xs

type Answer = Int
answer :: Answer -> IO ()
answer = print

solve :: [Int] -> Answer
solve = snd . inner 0 0 minBound maxBound
  where
    inner b s d p (x : xs)
      | x  <  p   = inner 1  0  d  x xs `add` (d, min b s)
      | x  == p   = inner b' s  d  p xs
      | d' == d   = inner b  s' d  p xs
      | d' >  d   = inner b  1  d' p xs
      | otherwise = inner b  s  d  p xs
      where
        d' = x - p
        b' = succ b
        s' = succ s
    inner b s d _ _ = (d, min b s)
    add (d, n) (c, m)
      | d > c     = (d, n)
      | otherwise = (d, n + m)
