题目描述

给定一个长度为 n 的整数序列，您的任务是查找连续的非空子数组中值的最大总和。

输入格式

第一行输入一个整数 n，表示序列的长度。

接下来一行 n 个整数,第i个整数为$a_i$，表示读入的序列元素。

输出格式

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

样例输入

5
-5 3 -1 3 2

样例输出

7

提示

• $1\leq n \leq 2·10^5$
• $-10^9\leq a_i \leq 10^9$