CF1359D.Yet Another Yet Another Task

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.

爱丽丝和鲍勃正在玩另一场纸牌游戏。这次的规则如下：在他们面前有一排 $n$ 张卡片，第 $i$ 张卡片的数值为 $a_i$。

首先，爱丽丝选择一个非空的连续卡片区间 $[l; r]$（其中 $l \le r$）。接着，鲍勃从该区间中移除恰好一张卡片 $j$（满足 $l \le j \le r$）。游戏的得分为该区间中剩余卡片的总值，即

$$a_l + a_{l + 1} + \dots + a_{j - 1} + a_{j + 1} + \dots + a_{r - 1} + a_r.$$

特别地，若爱丽丝选择的区间仅含一张卡片，则鲍勃移除该唯一卡片后，得分为 $0$。

爱丽丝希望使最终得分尽可能大；而鲍勃则会移除一张卡片，使得得分尽可能小。

爱丽丝应选择哪个区间，才能使最终得分达到最大？请输出这个最大可能得分。

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.

第一行包含一个整数 $n$（$1 \le n \le 10^5$）—— 卡片的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-30 \le a_i \le 30$）—— 卡片上的数值。

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

输出一个整数——游戏的最终得分。

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$.

在第一个例子中，Alice 选择区间 $[1;5]$ —— 即整行卡片。Bob 从该区间中移除编号为 $3$、值为 $10$ 的卡片。因此，最终得分为 $5 + (-2) + (-1) + 4 = 6$。

在第二个例子中，Alice 选择区间 $[1;4]$，于是 Bob 将移除编号为 $1$ 或 $3$、值为 $5$ 的卡片，使得答案为 $5 + 2 + 3 = 10$。

在第三个例子中，Alice 可以任选一个长度为 $1$ 的区间：$[1;1]$、$[2;2]$ 或 $[3;3]$。Bob 将移除其中唯一的一张卡片，因此得分为 $0$。若 Alice 选择其他任意区间，则得分将小于 $0$。