e-olymp
Competitions

December 4 - BMTK Programming School, High League

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 (1n106). 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.

Time limit 1 second
Memory limit 122.17 MiB
Input example #1
6
4 2 3 -7 8 1
Output example #1
11
Input example #2
8
2 -1 4 3 -8 6 -3 4
Output example #2
8
Input example #3
3
-12 -6 -1
Output example #3
-1