题目描述

给定N个数，求这N(1 <=N <= 100,000) 个数的某个连续子序列的累加和，保证这个连续子序列的累加和最大。

输入格式

第一行：一个整数N。(1 <=N <= 100,000) 接下来N行，每行一个整数P_i(-1,000 <= P_i <= 1,000)。表示第i个数。

输出格式

一个整数，表示子序列的最大连续累加和。

样例数据

input

7
-3
4
9
-2
-5
8
-3

output

14

数据规模与约定

20% 数据保证 $n \leq 20 $

60%数据保证 $n \leq 5000$

100% 数据保证 $ n \leq 100000 $

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$

注释

(4, 9, -2, -5, 8) => 14. 子序列不能为空！！