During a FIFA World Cup match, analysts record
Each moment has a momentum value
A positive value means the moment helped the team, and a negative value means the moment hurt the team.
A momentum streak is a non-empty contiguous segment of moments.
The score of a momentum streak is the sum of all momentum values inside it.
Your task is to find the maximum possible score of any momentum streak.
The first line contains a single integer KaTeX can only parse string typed expression — the number of moments.
The second line contains KaTeX can only parse string typed expression integers KaTeX can only parse string typed expression — the momentum values.
Print a single integer — the maximum possible score of a non-empty contiguous momentum streak.
Input
8
-2 3 -1 5 -6 4 2 -17The best momentum streak is from moment KaTeX can only parse string typed expression to moment KaTeX can only parse string typed expression.
Its score is KaTeX can only parse string typed expression.
Example 2:
Input
5
-8 -3 -10 -2 -6-2All values are negative, so the best non-empty streak contains only moment KaTeX can only parse string typed expression.