描述

给定一个序列a[n],求a[n]的所有连续子序列中所有数值的和的最大值
连续子序列即a[n]中连续的项组成的子序列

输入

第一行,一个整数n
第二行,n个整数,表示给定的序列

输出

一个整数,表示所有子序列和的最大值

输入样例

5
-1 2 -3 4 5

输出样例

9

样例说明

用一个区间[l,r]表示a[l]与a[r]之间形成连续子序列
则
区间[1,1]的和为-1
区间[1,2]的和为1
区间[1,3]的和为-2
区间[1,4]的和为2
区间[1,5]的和为7
区间[2,2]的和为2
区间[2,3]的和为-1
区间[2,4]的和为3
区间[2,5]的和为8
区间[3,3]的和为-3
区间[3,4]的和为1
区间[3,5]的和为6
区间[4,4]的和为4
区间[4,5]的和为9
区间[5,5]的和为5
综上,所有子序列的和的最大值为9

数据范围和限制

对于前30分的数据满足序列是单调递增的
对于前60分的数据满足a[n]中至少有一半的数是负数
对于60分的数据 n<=60000,且保证a[n]中至少有一个正数
对于100分的数据 n<=200000,-10000<a[i]<10000
时间限制1秒,空间限制256M