题目描述

给定 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 构成一个序列，请为这个序列寻找一个子串，使数字之和达到最大。子串是原序列中连续且保持顺序的一段数字，空串或序列全体都算原序列的子串。

输入格式

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

输出格式

单个整数：表示子串的最大和。

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 200$，
• 对于 $60\%$ 的数据，$1\leq n\leq 5000$，
• 对于 $100\%$ 的数据，$1\leq n\leq 200,000$。
• $-10000\leq a_i\leq 10000$

样例数据

输入:

5
1 2 -10 2 3

输出:

5

输入:

3
-1 -2 -3

输出:

0

输入:

3
3 -2 3

输出:

4