题目描述

Alice 和 Bob 现在正在玩另一场卡牌游戏。游戏规则如下。

有 $n$ 张卡牌从左往右排成一排，第 $i$ 张卡牌的数值为 $a_i$。

首先，Alice 选择这些卡牌中的连续一段 $[l,r](1 \le r)$（这也就是说，Alice会选择从第 $l$ 张卡牌到第 $r$ 张卡牌范围内的所有卡牌）。

然后，Bob 会从 Alice 选择的这些卡牌中移除去一张卡牌。注意：Bob 移除的这张卡牌需要在 Alice 所选择的卡牌中，这也就是说，如果 Bob 选择移除的卡牌是第 $j$ 张卡牌，则必然满足 $l \le j \le r$。

游戏的最终得分为出去 Bob 移除的那张卡牌外其余所有 Alice 选择的卡牌的数值之和。

Alice 希望使游戏的最终得分尽可能地大，Bob 希望使游戏的最终得分尽可能地小。

假设 Alice 和 Bob 都绝对聪明。

问：在此条件下能够获得的最终得分的最大值是多少？

输入格式

输入的第一行包含一个整数 $n(1 \le n \le 10^5)$，表示卡牌的数量。

输入的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n(-30 \le a_i \le 30)$，表示每张卡牌的数值。

输出格式

输出一个数值，表示能够获得的最终得分的最大值。

样例

5
5 -2 10 -1 4

6

8
5 2 5 3 -30 -30 6 9

10

3
-10 6 -15

0

说明/提示

样例解释

样例1中，Alice 选择区间 $[1,5]$，Bob 移除第 $3$ 张（数值为 $10$ 的）卡牌，最终得分为 $5 + (-2) + (-1) + 4 = 6$。

样例2中，Alice 选择区间 $[1,4]$，Bob 可以选择移除第 $1$ 或 $3$ 张（数值为 $5$ 的）卡牌，最终得分为 $5 + 2 + 3 = 10$。

样例3中，Alice 可以选择任意一个长度为 $1$ 的区间，然后 Bob 移除掉区间内的唯一一个元素，最终得分均为 $0$。如果 Alice 选择任何一个其它区间则最终得分都会小于 $0$。

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 10$
• 对于 $60\%$ 的数据，$n \le 1000$
• 对于 $100\%$ 的数据，$1 \le n \le 100000, -30 \le a_i \le 30$