Alice 和 Bob 正在玩另一个纸牌游戏。这次的规则如下。他们面前有一排 $$$n$$$ 卡片。第 $$$i$$$ 卡的价值为 $$$a_i$$$。
首先,Alice 选择一个非空的连续卡片段 $$$[l; r]$$$ ($$$l \le r$$$)。之后,Bob 从该段 $$$(l \le j \le r)$$$ 中删除一张卡片 $$$j$$$。游戏的得分为$$$(a_l + a_{l + 1} + \dots + a_{j - 1} + a_{j + 1} + \dots + a_{r - 1} + a_r)$$$段上剩余牌的总分。特别是,如果 Alice 选择只有一个元素的片段,那么 Bob 删除唯一一张卡片后的分数为 $$$0$$$。
Alice 想让分数尽可能大。鲍勃拿了一张分数尽可能小的牌。
Alice 应该选择哪个片段才能获得最大分数?输出最高分。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 卡的数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$-30 \le a_i \le 30$$$) — 卡片上的值。
输出
打印一个整数——游戏的最终得分。
示例
输入 #1
5 5 -2 10 -1 4
输出 #1
6
输入 #2
8 5 2 5 3 -30 -30 6 9
输出 #2
10
输入 #3
3 -10 6 -15
输出 #3
0
注意
在第一个示例中,Alice 选择了一段 $$$[1;5]$$$ — 整行卡片。 Bob 从段中删除了价值 $$$10$$$ 的卡 $$$3$$$。因此,最终得分为 $$$5 + (-2) + (-1) + 4 = 6$$$。
在第二个示例中,Alice 选择段 $$$[1;4]$$$,以便 Bob 删除值为 $$$5$$$ 的卡 $$$1$$$ 或 $$$3$$$,从而得到答案 $$$5 + 2 + 3 = 10$$$。
在第三个示例中,Alice 可以选择长度为 $$$1$$$ 的任意段:$$$[1;1]$$$、$$$[2;2]$$$ 或 $$$[3;3]$$$。鲍勃拿走了唯一的一张牌,因此得分为 $$$0$$$。如果 Alice 选择其他部分,那么答案将小于 $$$0$$$。