题目描述

译自 CCC2016 Senior T4. Combining Riceballs

Alphonse 有 $N$ 个美味的饭团，它们大小不一，摆放成一行。他想把最大的饭团让给自己的基友。他可以执行以下操作：

• 如果两个相邻的饭团大小相同，Alphonse 可以把它们合并成一个新的饭团。新饭团的大小是两个原饭团大小之和。它将占据两个原饭团先前占据的位置。

• 如果两个饭团大小相同，且它们之间只有一个饭团，Alphonse 也可以把它们合并成一个新的饭团。（中间的饭团大小没有规定。）新饭团的大小是三个原饭团大小之和，并占据三个原饭团先前的位置。

Alphonse 可以按照他的意愿执行任意次操作。

在执行 0 或更多次操作后，确定他应该把哪个饭团让给基友。

输入格式

第一行，一个整数 $N(1 \le N \le 400)$。

第二行，$N$ 个以空格分隔的整数，表示每个饭团的大小，按照从左到右的顺序给出。每个整数的上界为 $1\ 000\ 000$。

输出格式

输出 Alphonse 可以得到的最大的饭团大小。

样例 1

input

7
47 12 12 3 9 9 3

output

48

有一种可能的合并方案为：合并大小同为 $12$ 的两个饭团，得到一个大小为 $24$ 的饭团。然后合并大小同为 $9$ 的两个饭团，得到一个大小为 $18$。接着合并大小为 $3,18$ 和 $3$ 的三个饭团，得到一个大小为 $24$ 的饭团。最后合并大小同为 $24$ 的两个饭团，得到一个大小为 $48$ 的饭团。

样例 2

input

4
1 2 3 1

output

3

我们无法进行操作，所以答案为 $3$。

数据范围与提示

对于 $\frac1{15}$ 的数据，$N = 4$。

对于另外 $\frac2{15}$ 的数据，$N \le 10$。

对于另外 $\frac5{15}$ 的数据，$N \le 50$。