#QY0026. 原神圣遗物

原神圣遗物

题目背景

Dw最近正在玩《原神》,这是一款开放世界的RPG游戏,游戏里有一种圣遗物系统,Dw手中有很多圣遗物

题目要求

Dw有存放圣遗物的背包,背包有 nn 件圣遗物,圣遗物都有一些属性加成倍数,分别为 aiai ,可是这些圣遗物中也会有"debuff"出现(aiai 为负数),于是Dw找到了你帮忙,请你帮他选出一个圣遗物区间,区间必须是连续的,使区间内的圣遗物属性加成最高。

输入输出

输入

第一行一个整数 nn ,表示圣遗物个数 ,接下来 nn 个整数,表示每个圣遗物的属性加成数值

输出

一个正整数,表示最多的加成数值

测试样例

5
-1 1 -4 5 1
6

数据规模与约定

对于100%的数据,1n1041\leq n \leq 10^4

ai104ai \leq 10^4