配点 : $500$ 点

問題文

高橋君と $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$ 回以上餌をあげるまでにかかる費用の合計として考えられる最小値を出力してください。

制約

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

入力

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

$N$

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

出力

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

5
2 5 3 2 5

7

高橋君が $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$ 円であり、これが考えられる最小値です。

20
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62

426