將 n 堆石子繞圓形操場排放，現(xiàn)要將石子有序地合并成一堆。規(guī)定每次只能選相鄰的兩堆合并成新的一堆，并將新的一堆的石子數(shù)記做該次合并的得分。
請編寫一個(gè)程序，讀入堆數(shù) n 及每堆的石子數(shù)，并進(jìn)行如下計(jì)算：

1、選擇一種合并石子的方案，使得做 n?1 次合并得分總和最大。
2、選擇一種合并石子的方案，使得做 n?1 次合并得分總和最小。

輸入第一行一個(gè)整數(shù) n，表示有 n 堆石子。
第二行 n 個(gè)整數(shù)，表示每堆石子的數(shù)量。

輸出共兩行：
第一行為合并得分總和最小值，
第二行為合并得分總和最大值。

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

對于 100% 的數(shù)據(jù)，有 1≤n≤200。

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