题目描述

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

输入格式

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

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

输出格式

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

样例

输入

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

输出

16

提示

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

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

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

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