题目描述

有一个由 $N$ 张牌组成的牌堆，每一张牌上都写有一个非负整数。自顶部开始，第 $i$ 张牌上的数字为 $A_i$。

Snuke 将重复以下操作，直至牌堆里只剩两张卡为止：

• 从牌堆里选择三张连续的卡。
• 把三张卡中位于中间位置的卡吃掉。
• 把剩余的两张卡上的数字加上被吃掉的卡的数字后按照原来的顺序放回牌堆。

请找出最后剩下的两张牌上所写的数字之和最小是多少。

样例 $1$ 解释

通过执行以下操作，可以使剩余两张牌的数字之和最小：

• 最初，牌堆的数字自顶向下为 $3,1,4,2$。
• 选择自顶向下的前三张牌，吃掉写有数字 $1$ 的卡牌，在剩余的两张牌中每张牌的数字加 $1$，放回至原来位置。现在牌堆的数字自顶向下为 $4,5,2$。
• 选择自顶向下的前三张牌，吃掉写有数字$5$的卡牌，在剩余的两张牌中每张牌的数字加 $5$，放回至原来位置。现在牌堆的数字自顶向下为 $9,7$。
• 剩下的两张牌的数字之和为 $16$。