AT_agc035_d [AGC035D] Add and Remove

有一叠写有非负整数的卡片，共有 $N$ 张。自上而下第 $i$ 张卡片上写的整数为 $A_i$。 すぬけ君会重复以下操作，直到卡片只剩下 $2$ 张为止： - 选择连续的 $3$ 张卡片。 - 吃掉中间的那一张卡片。 - 将剩下的 $2$ 张卡片上的整数，各自加上被吃掉的卡片上的整数，并将结果写回这两张卡片上。 - 按原顺序将这 $2$ 张卡片放回原来的位置。 请你求出最后剩下的 $2$ 张卡片上的整数之和的最小值。

输入以以下格式从标准输入给出。 > $N$ $A_1$ $A_2$ $\ldots$ $A_N$

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

## 限制条件 - $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 翻译