题目描述

给出一个长度为n的整数列a，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度n; 第二行有n个整数，第i个整数表示序列的第i个数字$a_i$

输出格式

输出一行一个整数表示答案：最大子段和的值。

样例

样例输入

6
-2 11 -4 13 -5 -2

样例输出

20

数据范围与提示

n<=100