AT_abc251_e [ABC251E] Takahashi and Animals

高桥君和 $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$ 次所需的最小总费用。

### 限制条件 - $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$ 日元，这是可能的最小值。 由 ChatGPT 4.1 翻译