题目描述

小可要举办生日派对，邀请了 $N$ 位朋友围坐在圆桌旁（座位1、2、...、$N$，其中座位 $N$ 和座位 $1$ 相邻）。

小可有 $N$ 种装饰方案，每种方案可以重复使用：

• 方案1：装饰座位1和座位2，花费 $C_1$ 元
• 方案2：装饰座位2和座位3，花费 $C_2$ 元
• ...
• 方案$i$：装饰座位$i$和座位$(i+1)$，花费 $C_i$ 元
• ...
• 方案$(N-1)$：装饰座位$(N-1)$和座位$N$，花费 $C_{N-1}$ 元
• 方案$N$：装饰座位$N$和座位$1$，花费 $C_N$ 元

注意：座位是圆桌排列，所以方案$N$装饰的是座位$N$和座位$1$。

小可希望每个座位至少被装饰一次（同一个座位可以被多个方案装饰）。

请问：最少需要花费多少钱？

输入格式

第一行一个整数 $N$，表示座位数（也是方案数）。

第二行 $N$ 个整数 $C_1, C_2, \dots, C_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

提示

样例1解释

有5个座位，方案费用：2, 5, 3, 2, 5

选择方案1、3、4：

• 方案1（2元）：装饰座位1和2
• 方案3（3元）：装饰座位3和4
• 方案4（2元）：装饰座位4和5

总花费：2+3+2=7元，这是最小花费。

数据范围

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

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