問題文

伝説のパン職人であるBreadくんは、$N$ 個のフランスパンを持っています。 $i$ 個目のフランスパンの長さは $A_i$です。

Breadくんはフランスパンを$1$つにまとめ上げるための伝統的な儀式、「パン並べ」を行おうとしています。

まず、「パン並べ」の準備として、$i$ 個目のフランスパンが左から $i$ 番目に配置されるように、フランスパンを$1$列に並べます。そして、以下の操作を、フランスパンが1つになるまで繰り返します。

• 隣り合っているフランスパンを$2$つ選ぶ。$2$つの長さをそれぞれ $X,Y$ とする。この$2$つのフランスパンと $X \times Y$ ゴールドを使い、長さ $X+Y$ のフランスパンを$1$個作る。その後、列の右端か左端に新しいフランスパンを置く。使ったフランスパンは消える。

Breadくんはケチなので、できるだけ「パン並べ」に使用するゴールドの量を抑えたいと思っています。

Breadくんのために、使用するゴールドの量の最小値を求めてあげてください。

制約

• $2 \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^4$
• 入力はすべて整数

小課題

この問題にはサブタスクによる部分点が設定されています。

入力

$N$
$A_1$ $A_2$ $\dots$ $A_N$

出力

Breadくんが「パン並べ」で使うゴールドの量の最小値を出力してください。

サンプル

4
3 1 4 1

27

2
10000 10000

100000000

12
1 1 1 1 1 1 1 1 1 1 1 1

66