You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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$