Thylacine

Given the sequence of n integers. Find its nonempty subsequence of consecutive numbers, such that the sum of these numbers is maximal.

Input

First line contains number n (1 ≤ n ≤ 10^6). Second line contains the sequence elements, each of them is no more than 1000.

Output

Print the maximum sum of numbers in non-empty sub-sequence of consecutive numbers.

Examples