/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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 回以上餌をあげるまでにかかる費用の合計として考えられる最小値を出力せよ。
入力例 1
5 2 5 3 2 5
出力例 1
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 円であり、これが考えられる最小値です。
入力例 2
20 29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62
出力例 2
426
Score : 500 points
Problem Statement
Takahashi is with N animals. The N animals are called Animal 1, Animal 2, \ldots, Animal N.
Takahashi will perform the following N kinds of action. Each action can be performed any number of (possibly zero) times.
- Pay A_1 yen (the currency in Japan) to feed Animals 1 and 2.
- Pay A_2 yen to feed Animals 2 and 3.
- Pay A_3 yen to feed Animals 3 and 4.
- \cdots
- Pay A_i yen to feed Animals i and (i+1).
- \cdots
- Pay A_{N-2} yen to feed Animals (N-2) and (N-1).
- Pay A_{N-1} yen to feed Animals (N-1) and N.
- Pay A_N yen to feed Animals N and 1.
Note that the N-th action above feeds "Animals N and 1."
Print the minimum possible total cost to feed every animal at least once.
Constraints
- 2 \leq N \leq 3 \times 10^5
- 1 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print the minimum possible total cost to feed every animal at least once.
Sample Input 1
5 2 5 3 2 5
Sample Output 1
7
If Takahashi performs the 1-st, 3-rd, and 4-th actions once each, Animals 1, 2, 3, 4, and 5 are fed once, once, once, twice, once, respectively, so every animal is fed at least once. The total cost to do so is A_1 + A_3 + A_4 = 2 + 3 + 2 = 7 yen, which is the minimum possible.
Sample Input 2
20 29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62
Sample Output 2
426