Yet Another Yet Another Task

题意翻译

**Alice**和**Bob**正在玩另一场卡牌游戏。这次的规则如下： 首先,**Alice**选取一段不为空的连续区间$[l,r],(l\leq r)$,之后**Bob**移去这个区间的一张卡牌$j(l\leq j \leq r)$。这场游戏的得分就是区间剩余卡牌值的总和。特别的，如果**Alice**只选择了一张牌，那么最终的得分就是0. **Alice**想让这个得分足够大，而**Bob**为了让得分足够小，会取出一张这个区间中值最大的牌。现在询问**Alice**应该如何选择这个区间来使得自己的得分在所有情况中最大。输出最大值。

题目描述

Alice and Bob are playing yet another card game. This time the rules are the following. There are $ n $ cards lying in a row in front of them. The $ i $ -th card has value $ a_i $ . First, Alice chooses a non-empty consecutive segment of cards $ [l; r] $ ( $ l \le r $ ). After that Bob removes a single card $ j $ from that segment $ (l \le j \le r) $ . The score of the game is the total value of the remaining cards on the segment $ (a_l + a_{l + 1} + \dots + a_{j - 1} + a_{j + 1} + \dots + a_{r - 1} + a_r) $ . In particular, if Alice chooses a segment with just one element, then the score after Bob removes the only card is $ 0 $ . Alice wants to make the score as big as possible. Bob takes such a card that the score is as small as possible. What segment should Alice choose so that the score is maximum possible? Output the maximum score.

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the number of cards. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ -30 \le a_i \le 30 $ ) — the values on the cards.

输出格式

Print a single integer — the final score of the game.

输入输出样例

输入样例 #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

说明

In the first example Alice chooses a segment $ [1;5] $ — the entire row of cards. Bob removes card $ 3 $ with the value $ 10 $ from the segment. Thus, the final score is $ 5 + (-2) + (-1) + 4 = 6 $ . In the second example Alice chooses a segment $ [1;4] $ , so that Bob removes either card $ 1 $ or $ 3 $ with the value $ 5 $ , making the answer $ 5 + 2 + 3 = 10 $ . In the third example Alice can choose any of the segments of length $ 1 $ : $ [1;1] $ , $ [2;2] $ or $ [3;3] $ . Bob removes the only card, so the score is $ 0 $ . If Alice chooses some other segment then the answer will be less than $ 0 $ .