Given the sequence of n integers. Find its nonempty subsequence of consecutive numbers, such that the sum of these numbers is maximal.
First line contains number n (1 ≤ n ≤ 10^6
). Second line contains the sequence elements, each of them is no more than 1000.
Print the maximum sum of numbers in non-empty sub-sequence of consecutive numbers.