题目描述

高桥君和 $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

输入

5
2 5 3 2 5

输出

7

样例 2

输入

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$
• 输入均为整数

样例解释 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 翻译