sumup _ [] = []
sumup s (x:xs) =
  let s' = (s+x)
  in
    s':(sumup s' xs)

scan :: (Int,Int) -> [Int] -> (Int,Int)
scan (m,a) [] = (m,a)
scan (m,a) (x:xs) =
  let m' = min m x
      a' = max a (x-m)
  in
    scan (m',a') xs

ans (0:_) = []
ans (n:x) =
  let a = take n x
      s = 0:(sumup 0 a)
      s0= s!!0
      s1= s!!1
      (_,d) = scan (s0,s1-s0) s
      r = drop n x
  in
    d:(ans r)

main = do
  c <- getContents
  let i = map read $ lines c :: [Int]
      o = ans i
  mapM_ print o