问题描述

牧场养了 $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\times10^5$，$1\leq A_i \leq 10^9$，所有输入都是整数