80種天然稀缺礦物質提煉的精華

題目敘述

想必各位一定知道，金坷垃是由80種天然稀缺礦物質提煉的精華，那它究竟是怎麼被提煉的呢?在金坷垃生產基地，美國聖地牙哥國際農業集團，有一條巨大的傳輸鏈，80種礦物質被依序放在傳輸鏈的上面。每個礦物質都有自己的「氮磷鉀值」，「氮磷鉀值」會是一個int範圍的整數。傳輸鏈上相鄰的礦物質可以合併成一個新的礦物質，合併會消耗掉與他們「氮磷鉀值」總和相當單位的「氮磷鉀」數量，合併完後產生礦物質的「氮磷鉀值」就會是原來兩個礦物的「氮磷鉀值」總和，當所有的礦物融合成一個時金坷垃就完成了。
現在給你$N$個依序放在傳輸鏈上的礦物和他們的「氮磷鉀值」，請你輸出輸出產生金坷垃最少要消耗多少單位的「氮磷鉀」

輸入說明

第一行有一個數字$N$，$1 \leq N \leq 150$，接下來一行有N個正整數，依序表示傳輸鏈上礦物質的「氮磷鉀值」

輸出說明

請輸出產生金坷垃最少要消耗多少單位的「氮磷鉀」

範例輸入

3
1 2 3

範例輸出

提示

範例測資終止有兩種合併方法：

先合併1、2，產生「氮磷鉀值」為3的礦物質，在合併3、3，需要(1+2)+(3+3)=9單位的「氮磷鉀」
先合併2、3，產生「氮磷鉀值」為5的礦物質，在合併1、5，需要(2+3)+(1+5)=11單位的「氮磷鉀」

附記

這題有$O(N^2)$的算法喔，雖然$O(N^3)$ 會過

Judge Setting

run-time limit: 20 ms
memory limit: 13814400 byte
測資數量: 0