题目描述

小明发明了一个卡牌合并游戏，规则如下：

1. 初始时桌面上有自左向右排成一排的 $n$ 张卡牌，每张卡牌上写有一个整数分值。
2. 每次操作，小明可以选取当前序列最左边的连续若干张卡牌（至少 $2$ 张），将它们合并为一张新卡牌。新卡牌的分值等于被合并的那些卡牌的分值之和，合并后新卡牌插入序列最左端。
3. 初始总分为 $0$。每次合并操作后，新卡牌的分值会加到总分中。当序列只剩下一张卡牌时游戏结束，小明也可以在任意时刻主动结束游戏。

现在给出初始卡牌的分值序列，请你帮小明算出他能获得的最高总分。

输入格式

第一行一个正整数 $n$，表示卡牌数目。

接下来一行 $n$ 个以空格分隔的整数，第 $i$ 个数 $a_i$ 表示从左到右第 $i$ 张卡牌的分值。

输出格式

仅一行一个整数，表示小明能获得的最高总分。

样例

3
2 -1 2

4

7
-4 3 0 7 -3 -5 -3

9

提示

样例解释 1

最优策略：先合并最左侧两张卡牌（分值 $2$ 和 $-1$），总分增加 $2+(-1)=1$。合并后序列变为 $1, 2$。

再合并所有卡牌，总分增加 $1+2=3$，总分为 $4$。此时序列仅剩一张卡牌，游戏结束。

样例解释 2

最优策略：先合并最左侧四张卡牌（分值 $-4, 3, 0, 7$），总分增加 $(-4)+3+0+7=6$。合并后序列变为 $6, -3, -5, -3$。

再合并最左侧两张卡牌，总分增加 $6+(-3)=3$，总分为 $9$。此时无论如何操作均无法使总分继续增大，小明结束游戏。

数据范围与约定

测试点 $1\sim6$：$1\le n\le 16$，$|a_i|\le 100$。

测试点 $7\sim12$：$1\le n\le 10^3$，$|a_i|\le 100$。

测试点 $13\sim20$：$1\le n\le 10^5$，$|a_i|\le 10^5$。