题目描述

在一个圆形操场的四周摆放了 n 堆石子（n≤100），现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记为该次合并的得分。 编程，读入堆数 n 及每堆石子数（≤20），选择一种合并石子的方案，使得做 n-1 次合并，得分的总和最小；选择一种合并石子的方案，使得做 n-1 次合并，得分的总和最大。

例如，如图 9.6-1 所示的 4 堆石子，每堆石子数（从最上面的一堆开始按顺时针方向数）依次为 4、5、9、4，则 3 次合并得分总和最小的方案如图 9.6-2 所示，得分总和最大的方案如图 9.6-3所示。

输入格式

第 1 行为石子堆数 n，第 2 行为每堆石子数，每两个数之间用一个空格分隔。

输出格式

第 1 行为最小得分值，第 2 行为最大得分值。

样例数据

input

4
4 5 9 4

output

43
54

数据规模与约定

时间限制：$1 \text{s}$

空间限制：$256 \text{MB}$