题目描述

有 $n$ 只动物围成一圈，你可以花费 $a[i]$ 喂食动物 $i$ 和 $i+1$。特别地，你可以花费 $a[n]$ 喂食动物 $n$ 和 $1$。

输出喂食所有动物需要的最小花费。

输入格式

第一行输入 $N$

第二行输入 $A_1$ $A_2$ $\ldots$ $A_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

4
2 2 5 1

3

样例 3 解释

喂养第二和第四个动物即可使所有动物被喂养，花费为 $3$。

提示

• $2\ \leq\ N\ \leq\ 3\ \times\ 10^5$
• $1\ \leq\ A_i\ \leq\ 10^9$