题目描述

高橋君と $N$ 匹の動物がいます。 $N$ 匹の動物はそれぞれ動物 $1$ 、動物 $2$ 、$\ldots$ 、動物 $N$ と呼ばれます。

高橋君は下記の $N$ 種類の行動をそれぞれ好きな回数だけ（ $0$ 回でも良い）行います。

• $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$ に」餌をあげることに注意してください。

すべての動物にそれぞれ $1$ 回以上餌をあげるまでにかかる費用の合計として考えられる最小値を出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

すべての動物にそれぞれ $1$ 回以上餌をあげるまでにかかる費用の合計として考えられる最小値を出力せよ。

题目大意

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

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

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

提示

制約

• $2\ \leq\ N\ \leq\ 3\ \times\ 10^5$
• $1\ \leq\ A_i\ \leq\ 10^9$
• 入力はすべて整数

Sample Explanation 1

高橋君が $1$ 種類目、$3$ 種類目、$4$ 種類目の行動をそれぞれ $1$ 回ずつ行うと、 動物 $1$ に $1$ 回、動物 $2$ に $1$ 回、動物 $3$ に $1$ 回、動物 $4$ に $2$ 回、動物 $5$ に $1$ 回餌をあげることになり、すべての動物にそれぞれ $1$ 回以上餌をあげることができます。 このときにかかる費用の合計は $A_1\ +\ A_3\ +\ A_4\ =\ 2\ +\ 3\ +\ 2\ =\ 7$ 円であり、これが考えられる最小値です。