You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

译自 CCC2016 Senior T4「Combining Riceballs」

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

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

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

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

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

输入格式

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

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

输出格式

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

7
47 12 12 3 9 9 3

48

4
1 2 3 1

3

提示

样例解释 1

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

样例解释 2

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

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

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

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