题目描述

高橋有 $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$、$3$ 和 $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