题目背景

某公司统计了连续 $n$ 天的收益数据 $a_1, a_2, \dots, a_n$（正数表示盈利，负数表示亏损）。

公司想找出一段连续的时间区间，使得这段时间内的总收益最大，以便分析最佳经营策略。

题目描述

给定长度为 $n$ 的整数序列 $a[1..n]$，请找出一个连续的子区间 $[l, r]$（$1 \le l \le r \le n$），使得该区间内所有数的和最大。输出这个最大和。

输入格式

第一行一个正整数 $n$。

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

输出格式

输出一个整数，表示最大子段和。

样例输入

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

样例输出

6

样例解释

区间 $[4, 7]$ 的和为 $4 + (-1) + 2 + 1 = 6$，是所有连续子区间中最大的。

数据范围

$1 \le n \le 10^5$，$|a_i| \le 10^4$。