[ABC251E] 高桥君与动物

题目描述

有高桥君和 $N$ 只动物。$N$ 只动物分别被称为动物 $1$、动物 $2$、$\ldots$、动物 $N$。

高桥君可以分别按自己喜欢的次数（也可以为 $0$ 次）进行下述 $N$ 种行动：

• 支付 $A_1$ 日元，给动物 $1$ 和动物 $2$ 喂食。
• 支付 $A_2$ 日元，给动物 $2$ 和动物 $3$ 喂食。
• 支付 $A_3$ 日元，给动物 $3$ 和动物 $4$ 喂食。
• $\cdots$
• 支付 $A_i$ 日元，给动物 $i$ 和动物 $(i+1)$ 喂食。
• $\cdots$
• 支付 $A_{N-2}$ 日元，给动物 $(N-2)$ 和动物 $(N-1)$ 喂食。
• 支付 $A_{N-1}$ 日元，给动物 $(N-1)$ 和动物 $N$ 喂食。
• 支付 $A_N$ 日元，给动物 $N$ 和动物 $1$ 喂食。

请注意，上述第 $N$ 种行动是「给动物 $N$ 和动物 $1$ 喂食」。

请输出让所有动物至少被喂食 $1$ 次所需的最小总费用。

输入格式

输入通过标准输入按以下形式给出：

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

输出格式

输出让所有动物至少被喂食 $1$ 次所需的最小总费用。

输入输出样例 #1

输入 #1

5
2 5 3 2 5

输出 #1

7

输入输出样例 #2

输入 #2

20
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62

输出 #2

426

说明/提示

限制条件

• $2 \leq N \leq 3 \times 10^5$
• $1 \leq A_i \leq 10^9$
• 输入均为整数

样例解释 1

当高桥君分别进行第 $1$、第 $3$、第 $4$ 种行动各 $1$ 次时，动物 $1$ 被喂食 $1$ 次，动物 $2$ 被喂食 $1$ 次，动物 $3$ 被喂食 $1$ 次，动物 $4$ 被喂食 $2$ 次，动物 $5$ 被喂食 $1$ 次，所有动物都至少被喂食 $1$ 次。此时总费用为 $A_1 + A_3 + A_4 = 2 + 3 + 2 = 7$ 日元，这是可能的最小值。