問題文

きつねのしえるは川で釣りをしていた．黒くて細長い魚を手に入れることができたので，その場で切り刻んで刺身にして食べることにした．

魚は体長が N センチメートルある．奇妙なことに，この魚は身体の部分ごとに密度が異なっていた． 魚の身体を頭から 1 センチメートルごとに区切って番号を 1, 2, ..., N と付けるとき，身体の i 番目の部分の重みは w_i であった． 魚の i 番目から j 番目までの部分を [i..j] と表すことにする． 最初，しえるは魚の身体 [0..N-1] を 1 枚だけ持っていると見なせる．しえるはこれを切っていき最終的に N 個に分割された魚の身体 [0..0], [1..1], ..., [N-1..N-1] を得たい．

しえるは今野外におり，まな板などを持っていないので，次のようなアクロバティックな方法で魚の身体を切っていくことにした ： まず，魚の身体を 1 枚取る．これを [i..j] とする．この魚の身体は長さが少なくとも 2 センチメートル以上でなければならない．すなわち， j-i ≥ 1 でなければならない．次に，それを空中に投げる．そして日本刀を手に持ち，宙に舞う魚を真っ二つに切る．このとき，しえるは強靭な運動神経によって任意の位置でこの魚を切ることができるが，必ず 1 センチメートル区切りの位置で切るものとする．これにより，元の魚の身体 [i..j] を，任意の切断位置 k (i ≤ k < j) によって，[i..k] と [k+1..j] の 2 つに分割するのである． このアクロバティックな方法で魚の身体を 2 つに切るとき，元の身体の重さ (=w_i+w_i+1+...+w_j) だけコストがかかる．

しえるは，魚のすべての部分を 1 センチメートル区切りに切るのにかかるコストの合計値を最小にしたい．

N\\
w1\ w2\ ...\ wN

入出力例

入力例 1

3
1 2 3

出力例 1

9

まず，魚全体を 2 番目と 3 番目の部分の間で切る．これには 1+2+3 = 6 のコストがかかる． 次に，1 番目と 2 番目の部分の間で切る．これには 1+2=3 のコストがかかる．合計で 6+3=9 のコストがかかり，これが最善手である．

入力例 2

6
9876543210 9876543210 9876543210 9876543210 9876543210 9876543210

出力例 2

158024691360

入力例 3

10
127 131 137 139 149 151 157 163 167 173

出力例 3

5016