Description

给出一串整数$ a[1]，a[2],a[3],...,a[n] $,求出它最大的子序列和,即找出 $1 \le i \le j \le n$,使$a[i]+a[i+1]+....+a[j]$最大。

Input Format

第1行1个整数n,表示整数序列的个数。

第2行有n个整数,表示a[i],$1 \le i \le n$。

Output Format

输出一行一个数，表示最大的子序列和。

10
3 1 -6 1 7 5 -2 5 -100 10

16

Hint

对于30%的数据满足:$n<10^2$。

对于50%的数据满足:$n<10^4$。

对于80%的数据满足:$n<10^6$。

对于100%的数据满足:$n<10^8$。