题目描述

小可养了 $N$ 只可爱的动物，它们分别叫做动物 $1$ 、动物 $2$ 、...、动物 $N$。

小可每天会给这些动物喂食，她有 $N$ 种不同的喂食方式，每种方式可以重复使用（也可以不用）：

• 花费 $A_1$ 元，给动物 $1$ 和动物 $2$ 喂食
• 花费 $A_2$ 元，给动物 $2$ 和动物 $3$ 喂食
• 花费 $A_3$ 元，给动物 $3$ 和动物 $4$ 喂食
• ...
• 花费 $A_i$ 元，给动物 $i$ 和动物 $(i+1)$ 喂食
• ...
• 花费 $A_{N-2}$ 元，给动物 $(N-2)$ 和动物 $(N-1)$ 喂食
• 花费 $A_{N-1}$ 元，给动物 $(N-1)$ 和动物 $N$ 喂食
• 花费 $A_N$ 元，给动物 $N$ 和动物 $1$ 喂食

请注意最后一种喂食方式是给动物 $N$ 和动物 $1$ 喂食，形成了一个循环。

现在小可想确保每只动物至少被喂食一次，请问她最少需要花费多少钱？

输入格式

第一个整数 $n$ ，表示动物的数量和喂食方式。

接下来一行 $n$ 个整数，以空格隔开，表示喂食方式对应的费用 $A_i$。

输出格式

输出确保每只动物至少被喂食一次的最小花费。

样例

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

提示

样例1解释

小可如果选择第1种、第3种和第4种喂食方式各一次：

• 动物 $1$ 被喂1次
• 动物 $2$ 被喂1次
• 动物 $3$ 被喂1次
• 动物 $4$ 被喂2次
• 动物 $5$ 被喂1次 这样所有动物都被喂食至少一次，总花费为 $2 + 3 + 2 = 7$ 元，这是最小的可能花费。

数据范围

前 $30\%$的数据,$2 \leq n \leq 20$

$100\%$的数据，$2\ \leq\ n\ \leq\ 3\ \times\ 10^5 ，$$1\ \leq\ A_i\ \leq\ 10^9 ，$所有输入都是整数