时间限制： 1.0 秒

空间限制： 512 MB

题目描述

给出一个整数序列 $S$，其中有 $N$ 个数，定义其中一个非空连续子序列 $T$ 中所有数的和为 $T$ 的“序列和”。

对于 $S$ 的所有非空连续子序列 $T$，求最大的序列和。

输入格式

从标准输入读入数据。

第一行包含一个整数 $N~(1 \le N \le 10^6)$。

第二行包含 $N$ 个 $[-10^9, 10^9]$ 之间的整数，表示序列中的元素。

输出格式

输出到标准输出。

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

10
-2 6 6 5 3 0 -9 5 9 6

31

提示

你需要一个 $O(n)$ 的算法获得全部分数。