题目描述

有一叠 $N$ 张卡片，每张卡片上都写着一个非负整数。从顶部开始，第 $i$ 张卡片上的整数为 $A_i$。

Snuke 会重复以下操作，直到剩下两张卡片：

• 从卡片堆中选择三张连续的卡片。
• 吃掉这三张卡片中间的那张。
• 对于其他两张卡片，将它们上面的整数与被吃掉的卡片上的整数相加，然后将结果写在卡片上。
• 将两张卡片放回最初的位置，不改变它们的顺序。

找到剩下的最后两张卡片上整数的最小可能和。

约束条件

• $2 \leq N \leq 18$
• $0 \leq A_i \leq 10^9 (1 \leq i \leq N)$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $A_1$ $A_2$ $...$ $A_N$

输出

打印剩下的最后两张卡片上整数的最小可能和。

示例输入1

4
3 1 4 2

示例输出1

16

我们可以通过以下步骤将剩下的最后两张卡片上整数的和最小化：

• 初始时，卡片上的整数从顶部到底部依次为 $3$，$1$，$4$，$2$。
• 选择从顶部开始的第一张、第二张和第三张卡片。吃掉中间写着 $1$ 的那张卡片，将另外两张卡片上的整数都加上 $1$，然后将它们放回最初的位置。此时卡片上的整数从顶部到底部依次变为 $4$，$5$，$2$。
• 选择从顶部开始的第一张、第二张和第三张卡片。吃掉中间写着 $5$ 的那张卡片，将另外两张卡片上的整数都加上 $5$，然后将它们放回最初的位置。此时卡片上的整数从顶部到底部依次变为 $9$ 和 $7$。
• 剩下的最后两张卡片上整数的和为 $16$。

示例输入2

6
5 2 4 1 6 9

示例输出2

51

示例输入3

10
3 1 4 1 5 9 2 6 5 3

示例输出3

115