题目描述

有一叠写有非负整数的卡片，共有 $N$ 张。自上而下第 $i$ 张卡片上写的整数为 $A_i$。

すぬけ君会重复以下操作，直到卡片只剩下 $2$ 张为止：

• 选择连续的 $3$ 张卡片。
• 吃掉中间的那一张卡片。
• 将剩下的 $2$ 张卡片上的整数，各自加上被吃掉的卡片上的整数，并将结果写回这两张卡片上。
• 按原顺序将这 $2$ 张卡片放回原来的位置。

请你求出最后剩下的 $2$ 张卡片上的整数之和的最小值。

输入格式

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

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

请输出最后剩下的 $2$ 张卡片上的整数之和的最小值。

样例 1

输入

4
3 1 4 2

输出

16

样例 2

输入

6
5 2 4 1 6 9

输出

51

样例 3

输入

10
3 1 4 1 5 9 2 6 5 3

输出

115

说明/提示

限制条件

• $2 \leq N \leq 18$
• $0 \leq A_i \leq 10^9\ (1 \leq i \leq N)$
• 所有输入均为整数。

样例解释 1

通过以下操作，可以使最后剩下的 $2$ 张卡片上的整数之和最小：

• 最初，卡片上的整数依次为 $3, 1, 4, 2$。
• 选择第 $1,2,3$ 张卡片，吃掉第 $2$ 张卡片（上面写着 $1$），剩下的两张卡片各自加上 $1$，放回原位。此时卡片上的整数依次为 $4, 5, 2$。
• 选择第 $1,2,3$ 张卡片，吃掉第 $2$ 张卡片（上面写着 $5$），剩下的两张卡片各自加上 $5$，放回原位。此时卡片上的整数依次为 $9, 7$。
• 最后剩下的 $2$ 张卡片上的整数之和为 $16$。

由 ChatGPT 4.1 翻译