在一个圆形操场的四周摆放了 $n$ 堆石子，现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记为该次合并的得分。 请编写一个程序，读入堆数 $n$ 及每堆的石子数，并进行如下计算：（均不超过 $10000$），
- 选择一种合并石子的方案，使得做 $n-1$ 次合并，得分的总和最小；
- 选择一种合并石子的方案，使得做 $n-1$ 次合并，得分的总和最大。
例如，如图 $9.6-1$ 所示的 $4$ 堆石子，每堆石子数（从最上面的一堆开始按顺时针方向数）依次为 $4$、$5$、$9$、$4$，则 $3$ 次合并得分总和最小的方案如图 $9.6-2$ 所示，得分总和最大的方案如图 $9.6-3$所示。
输入格式
第一行包含整数 $n$，表示共有 $n$ 堆石子。
第二行包含 $n$ 个整数，分别表示每堆石子的数量。
输出格式
输出共两行：
第一行为合并得分总和最小值，
第二行为合并得分总和最大值。
数据范围
$1 \le n \le 200$
样例输入
4
4 5 9 4
样例输出
43
54
提示
