搬运水果

在果园里，n 堆果实排成一个环形，第 i 堆果实的重量为 a_i。果农需要将所有果实合并成一堆。合并规则如下：

（1）每次只能合并相邻的两堆，新堆的重量为两堆重量之和；

（2）每次合并消耗的体力等于新堆的重量；

（3）合并后新堆与剩余堆仍保持环形排列。

请设计合并顺序，求出合并全过程消耗的最小总体力与最大总体力。

时间限制：1000ms内存限制：256MB

输入格式

第一行：整数 n，表示果实堆数；

第二行：n 个整数 a₁、a₂、……、a_n，表示每堆果实的重量。

输出格式

第一行：最小总体力消耗；

第二行：最大总体力消耗。

输入样例

4
4 5 9 4

输出样例

43
54

数据范围：

1≤n≤100，1≤a_i≤1000。

最小总体力消耗：按照果实重量从小到大排序后合并的顺序计算出的总体力消耗。
最大总体力消耗：先合并重量最大的两堆，再依次合并剩下的堆，直到合并成一堆。

这个问题可以通过动态规划来解决。首先，我们需要明确状态的定义。假设我们定义dp[i][j]为合并第i堆到第j堆果实时所需要的最小体力消耗或最大体力消耗。

对于最小总体力消耗：
我们可以按照果实重量从小到大排序，然后依次合并相邻的两堆。这样，每次合并的两堆果实的重量和都会是最小的，从而消耗的体力也会最小。我们可以使用动态规划来计算这个值。状态转移方程为：dp[i][j] = dp[i][k] + dp[k+1][j] + sum[j]-sum[i]（其中sum为前缀和数组，表示前i堆果实的总重量）。这样，我们可以计算出合并所有果实所需的最小总体力消耗。

对于最大总体力消耗：
我们可以先合并重量最大的两堆，这样新堆的重量也会是最大的。然后，我们依次合并剩下的堆，每次都选择合并后新堆重量最大的情况，直到合并成一堆。这样，我们可以保证每次合并消耗的体力都是最大的。同样地，我们可以使用动态规划来计算这个值。状态转移方程为：dp[i][j] = max(dp[i][k]+dp[k+1][j]+sum[j]-sum[i])（其中sum为前缀和数组）。这样，我们可以计算出合并所有果实所需的最大总体力消耗。

最后，我们只需要输出计算得到的最小总体力消耗和最大总体力消耗即可。