题目描述

补给队沿途经过 $n$ 个站点，第 $i$ 个站点会让总补给量变化 $a_i$。数值可以为正，也可以为负。

现在需要选择一段连续且非空的行程，使得这段行程中所有站点的补给变化量之和最大。

请输出这个最大值。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一行一个整数，表示连续非空子段的最大和。

样例 #1

样例输入 #1

7
2 -4 3 -1 2 -4 3

样例输出 #1

4

数据范围