题目描述

给你一个长度为 $n$ 的序列 $a = \{ a_1, a_2, \ldots, a_n \}$。

你需要在序列 $a$ 中选择连续的一段元素（至少选择一个元素），且要求这段数字之和最大。

即 —— 你需要选择两个下标 $l, r$，满足 $1 \le l \le r \le n$ 且 $\sum\limits_{i=l}^r a_i$ 最大，并输出这个最大的 $\sum\limits_{i=l}^r a_i$ 。

输入格式

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

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n$，以空格分隔。

输出格式

输出一个整数，表示 $\max\limits_{1 \le l \le r \le n} \{ \sum\limits_{i=l}^r a_i \}$ 的值。

样例

4
-3 2 -1 4

5

3
-2 -3 -4

-2

6
-2 5 -3 -1 6 -5 3

7

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 1000$，$-1000 \le a_i \le 1000$
• 对于 $100\%$ 的数据，$1 \le n \le 10^5$，$-10^9 \le a_i \le 10^9$