高桥君与动物们

题目描述

高桥君与 $N$ 只动物在一起。 这 $N$ 只动物称为动物 $1$、动物 $2$、$\ldots$、动物 $N$。

高桥君将执行以下 $N$ 种动作。每种动作可以执行任意次（可能为 $0$ 次）。

支付 $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$”。

求让每只动物至少被喂食一次所需的最小总花费。

输入格式

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

N
A_1 A_2 … A_N

输出格式

打印让每只动物至少被喂食一次所需的最小总花费。

样例

5
2 5 3 2 5

7

如果高桥君将第 $1$、$3$、$4$ 种动作各执行一次，则动物 $1$、$2$、$3$、$4$、$5$ 分别被喂食 $1$、$1$、$1$、$2$、$1$ 次，因此每只动物都至少被喂食了一次。 此时总花费为 $A_1 + A_3 + A_4 = 2 + 3 + 2 = 7$ 日元，这是最小可能的。

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

426

数据范围

• $2 \le N \le 3 \times 10^5$
• $1 \le A_i \le 10^9$
• 输入中的所有值均为整数。