[CCC2016] 合并饭团

**译自 [CCC2016](https://cemc.math.uwaterloo.ca/contests/computing/2016/index.html) Senior T4「[Combining Riceballs](https://cemc.math.uwaterloo.ca/contests/computing/2016/stage%201/seniorEn.pdf)」** 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$。