原題來自：NOIP 2006

在 Mars 星球上，每個(gè) Mars 人都隨身佩帶著一串能量項(xiàng)鏈。在項(xiàng)鏈上有 N 顆能量珠。能量珠是一顆有頭標(biāo)記和尾標(biāo)記的珠子，這些標(biāo)記對(duì)應(yīng)著某個(gè)正整數(shù)。并且，對(duì)于相鄰的兩顆珠子，前一顆珠子的尾標(biāo)記必定等于后一顆珠子的頭標(biāo)記。因?yàn)橹挥羞@樣，通過吸盤——Mars 人吸收能量的器官的作用，這兩顆珠子才能聚合成一顆珠子，同時(shí)釋放出可被吸盤吸收的能量。如果一顆能量珠頭標(biāo)記為 m，尾標(biāo)記為 r，后一顆能量珠頭標(biāo)記為 r，尾標(biāo)記為 n，則聚合后釋放出 m×r×n Mars單位的能量，新珠子頭標(biāo)記為 m，尾標(biāo)記為 n。

當(dāng)需要時(shí)，Mars 人就用吸盤夾住相鄰的兩顆珠子，通過聚合得到能量，直到項(xiàng)鏈上只剩下一顆珠子為止。顯然，不同的聚合順序得到的總能量是不一樣的。請(qǐng)?jiān)O(shè)計(jì)一個(gè)聚合順序使得一串珠子聚合后釋放出的總能量最大。

例如，設(shè) N=4，四顆珠子頭標(biāo)記與尾標(biāo)記分別為 (2,3),(3,5),(5,10),(10,2)。我們用記號(hào) ? 表示兩顆珠子的聚合操作，(j?k) 表示 j,k 兩顆珠子聚合后釋放出的能量，則4,1兩顆珠子聚合后所釋放的能量為(4?1)=10×2×3=60，這一串項(xiàng)鏈可以得到最優(yōu)值的一個(gè)聚合順序所釋放出的總能量為(((4?1)?2)?3)=10×2×3+10×3×5+10×5×10=710
現(xiàn)在給你一串項(xiàng)鏈，項(xiàng)鏈上有 n 顆珠子，相鄰兩顆珠子可以合并成一個(gè)，合并同時(shí)會(huì)放出一定的能量，不同珠子合并放出能量不相同，請(qǐng)問按怎樣的次序合并才能使得釋放的能量最多？

第一行一個(gè)正整數(shù) n
第二行 n 個(gè)不超過 1000 的正整數(shù)，第 i(1≤i≤n) 個(gè)數(shù)為第 i 顆珠子的頭標(biāo)記，當(dāng) i≠n 時(shí)第 i 顆珠子的尾標(biāo)記等于第 i+1 顆珠子的頭標(biāo)記，當(dāng) i=n 時(shí)第 i 顆珠子的尾標(biāo)記等于第 1 顆珠子的頭標(biāo)記。

至于珠子的順序，你可以這樣確定：將項(xiàng)鏈放在桌面上，不要出現(xiàn)交叉，隨機(jī)指定一顆珠子為第一顆珠子，按順時(shí)針確定其它珠子的順序。

輸出只有一行，一個(gè)不超過 2.1×10⁹ 的正整數(shù)，表示最優(yōu)聚合順序所釋放的能量。

數(shù)據(jù)范圍與提示：

對(duì)于 100% 的數(shù)據(jù)，4≤n≤100。

信息學(xué)一本通 動(dòng)態(tài)規(guī)劃