Takahashi and Animals

题目描述

Takahashi 和 $N$ 只动物在一起。 这 $N$ 只动物被称为 动物 $1$、动物 $2$、$\ldots$、动物 $N$。 Takahashi 将执行以下 $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$”。 打印至少喂养每只动物一次所需的最小可能总费用。

输入格式

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

输出格式

打印至少喂养每只动物一次所需的最小可能总费用。

5
2 5 3 2 5

7

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

426

提示

$2 \leq N \leq 3 \times 10^5$ $1 \leq A_i \leq 10^9$ 输入中的所有值都是整数。如果 Takahashi 各执行一次第 $1$、第 $3$ 和第 $4$ 种操作，动物 $1$、$2$、$3$、$4$、$5$ 分别被喂了一次、一次、一次、两次、一次，因此每只动物至少被喂一次。 这样做的总费用为 $A_1 + A_3 + A_4 = 2 + 3 + 2 = 7$ 日元，这是可能的最小值。

标签: AtCoder|abc251E

来源

AtCoder|abc251E