该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem Description

（Hearts of Iron IV）是由瑞典游戏发行商Paradox Interactive开发的一款著名的二战模拟游戏。youngmagician最近迷上了这款游戏，在游戏中每个部队有“对人员杀伤”这个属性，后简称为攻击力,由于开启了奇怪的mod，youngmagician手下的师团们有些攻击力为负数，现在youngmagician要发动进攻了，它可以框选一个连续区间内的所有军队，这支军队的总攻击力为选中的师团的攻击力总和，（特别的，如果一个师团不选择，那么这个军队攻击力视为0），你能帮忙计算出youngmagician能调动的最高军队的攻击力吗？

Input Format

一个整数,n,表示师团的数量。 接下来n个数字，第i个数字表示第i个师团的攻击力

Output Format

一个数字，表示军队的最大攻击力。

Sample

样例输入

6
1 1 -4 5 1 4

样例输出

10

样例解释：选择后三个军队，攻击力和为10

Hint

对于所有数据，保证$1\leq n \leq 1e5$，军队攻击力$1\leq |v| \leq 1e6$