题目描述

将 $n$ 堆石子绕圆形操场排放，第 $i$ 堆石子的数量为 $a_i$。现在要将石子有序地合并成一堆。规定每次只能选择相邻的两堆合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

请计算：

1. 选择一种合并方案，使得做 $n-1$ 次合并后的得分总和最小；
2. 选择一种合并方案，使得做 $n-1$ 次合并后的得分总和最大。

输入格式

第一行包含一个整数 $n$，表示石子堆数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示每堆石子的数量。

输出格式

输出两行。

第一行输出合并得分总和的最小值。

第二行输出合并得分总和的最大值。

样例

4
4 5 9 4

43
54

数据范围与提示

• $1 \le n \le 200$
• $1 \le a_i \le 10000$

来源

一本通 5.1 例 1