You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

青春的风景

题目背景

蒙自一中的校门口种着 $n$ 棵树。

又到了夏天，到了一年纳新的时候，诸多家长和学生在校门口合照留念，留下属于他们的青春的风景。

题目描述

这些同学和家长会在这排树门口合照。每棵树都有自己的颜值。（因为有的树奇丑无比，所以颜值可能是负数）。

这些同学和家长希望找到颜值总和最高的一段来拍照。

（因为是拍照，所以必须是连续的一段）。

假设照片有无穷大，也就是说无论多少棵树，照片都能排的下。

请你输出这个最大颜值子段的子段之和。

（注意：一棵树都不选，也可以作为一种方案）。

输入格式

输入第一行一个整数 $n$，表示校门口树的数量。

接下来一行 $n$ 个整数，表示从左到右每一棵树的颜值。

输出格式

输出一个整数，表示这个最大颜值子段的和。

5
1 2 3 4 5

15

5
1 2 -7 3 4

7

7
1 2 3 4 -5 6 7

18

样例解释

对于样例1和3，全部选完可以得到最大的颜值和。

对于样例2，选择 $3,4$ 这两棵树可以得到最大的颜值和。

数据范围

对于 $20\%$ 的数据， $1\le n\le 5000$。

对于另外 $20\%$ 的数据，所有树的颜值都是正数。

对于另外 $20\%$ 的数据，能保证不选择任意一棵树是最优解。

对于 $100\%$ 的数据，保证 $1\le n\le 10^6, -10^9\le 树的颜值 \le 10^9$。