说明

题目背景

小凯在寒假尝试开了一个小卖部，但是因为没经验，动不动就会亏损。马上要过年了，小凯的妈妈想问问小凯的经营情况，小凯希望挑出一段利润最大的日期把经营情况告诉妈妈，请你帮帮他。

题目描述

小凯的小卖部一共经营了n天，每天都有一个盈亏金额（正数表示盈利、负数表示亏损），请你从中挑出连续一段日期，且这段日期的总盈利最大/亏损最少，并输出盈亏金额

输入格式

一个n，表示共经营n天

接下来一行n个整数，表示每天的盈亏金额

输出格式

一个整数，表示连续一段日期使得总盈利最大/亏损最少的盈亏金额

样例

5
-2 3 4 -1 9

15

提示

样例解释

第二天到第五天的连续日期盈利最多

数据范围，对30%的数据，n<=100

对100%的数据，n<=100000（注意：通常当n超过10000时，计算机1秒时间内没法做完一个二重循环，而n为100000可能需要运算一个小时以上，导致程序超时）