题目描述

给定一个数字序列 $A1,A2,....,An$ ,求 i , j ( $1 \le i \le j \le n$ ),使得 $Ai+.....+Aj$ 必须是连续的和最大,输出这个最大和。

输入格式

第1行：输入一个 n ，表示数字序列的个数。 $1 \le n \le 10^5$
第2行：输入 n 个元素的值。

输出格式

输出只有一行，最大连续子序列的和。

样例

6
-2 11 -4 13 -5 -2

20

10
-2 13 12 9 14 -10 2 9 -6 2

49