题目描述

将若干个整数排成一排，选取其中一截相邻的数相加，得到的和称为连续和。

现在给定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.

子序列不能为空！！