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.

题目描述：

大魔法师塔子哥有一个成名绝招，名为生灵涂炭术。该禁咒所到之处寸草不生，万物归 $0$ ，但是塔子哥一生可以使用的次数只有三次。

在塔子哥的世界里充斥着正负两种能量，正能量对人体有益，而负能量对人体是有害的。

已知地图上有 $n$ 个排成一列的地域，每个地域的能量都不一样，可以用一个数字来代表某个地域中正负能量的总数，正数代表正能量比负能量多，反之亦然。

塔子哥在他的前半生使用了一次生灵涂炭术，现在他能使用生灵涂炭术的次数只剩下了两次，现在塔子哥可以对任何一个连续的区域使用生灵涂炭术，使用之后，无论该连续区域中能量有多少，都会清0。

塔子哥希望天地间的正能量最多，他想知道在他使用了技能以后能使得天地间的正能量最多为多少？（如果天地间都是正能量，不使用技能也是可以的）

输入描述

输入第一行仅包含一个正整数 $n$ ( $1\le n \le 100000$ )，表示地域数量。

输入第二行包含 $n$ 个整数，每个整数代表一个地域的能量总和,保证这个数值的绝对值不大于 $100000$ 。

输出仅包含一个整数，即正能量最多为多少。

输入

5
5 -10 6 1 -5

输出

样例解释

显然把 $\{-10\}$ 和 $\{-5\}$ 删掉之后，余下的和为 $12$ 。