题目背景

一只股票连续 n 天有涨跌（涨为正、跌为负）。股民想找一段连续交易区间（非空），使这段时间的总涨跌最大。

题目描述

给定 n 天的涨跌值，输出最大连续子段和（子段非空）。

输入格式

第一行一个整数 n。第二行 n 个整数。

输出格式

一个整数，表示最大连续子段和。

输入输出样例

9
-2 1 -3 4 -1 2 1 -5 4

6

样例 1：子段 [4,-1,2,1] 的和为 6，最大。

说明/提示

1 ≤ n ≤ 10⁵，-10⁴ ≤ 数值 ≤ 10⁴。子段不能为空。