题目描述

小明在玩一个收集能量球的游戏。他有 $N$ 个能量球排成一行，每个能量球有一个能量值。他可以通过以下操作合并能量球：

• 如果两个相邻的能量球能量值相同，小明可以将它们合并成一个新的能量球。新能量球的能量值是原来两个能量球的能量值之和，并且占据原来两个能量球的位置。

• 如果两个能量球的能量值相同，并且它们之间恰好只有一个能量球（中间能量球的能量值任意），小明也可以将它们合并成一个新的能量球。新能量球的能量值是这三个能量球的能量值之和，并占据原来三个能量球的位置。

小明可以执行任意多次操作（包括零次）。

在操作之后，小明想知道他能得到的最大能量球的能量值是多少。

输入格式

第一行一个整数 $N$ $(1 \le N \le 400)$，表示能量球的个数。

第二行 $N$ 个整数，表示每个能量球的初始能量值，按照从左到右的顺序给出。每个整数不超过 $1\,000\,000$。

输出格式

输出一个整数，表示小明能得到的最大能量球的能量值。

样例

7
47 12 12 3 9 9 3

48

4
1 2 3 1

3

样例解释

样例解释 1

一种可能的合并方式：

• 合并两个能量值为 $12$ 的能量球，得到一个能量值为 $24$ 的能量球。
• 合并两个能量值为 $9$ 的能量球，得到一个能量值为 $18$ 的能量球。
• 合并能量值为 $3$、$18$、$3$ 的三个能量球（两边的 $3$ 相同，中间是 $18$），得到一个能量值为 $24$ 的能量球。
• 最后合并两个能量值为 $24$ 的能量球，得到能量值为 $48$ 的能量球。

样例解释 2

无法进行任何合并，因此最大能量值为 $3$。

数据范围

• 总共 $15$ 个测试点。
• 对于 $1/15$ 的数据，$N = 4$。
• 对于 $2/15$ 的数据，$N \le 10$。
• 对于 $5/15$ 的数据，$N \le 50$。
• 对于所有数据，$1 \le N \le 400$，能量值 $\le 10^6$。