分数: 500 点
问题陈述
高桥与 N 动物。 的 N 动物被称为动物 1, 动物 2, \ldots, 动物 N.
高桥将执行以下操作 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."
打印每只动物至少喂养一次的最低可能总成本。
约束
- 2 \leq N \leq 3 \times 10^5
- 1 \leq A_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N
输出
打印每只动物至少喂养一次的最低可能总成本。
示例输入 1
5 2 5 3 2 5
示例输出 1
7
如果高桥执行 1-st, 3-rd,和 4- 第一次动作,动物 1, 2, 3, 4,和 5 分别被喂食一次、一次、一次、两次、一次,因此每只动物至少被喂食一次。 这样做的总成本是 A_1 + A_3 + A_4 = 2 + 3 + 2 = 7 日元,这是可能的最低金额。
示例输入 2
20 29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62
示例输出 2
426