题目描述

在一个圆形操场的四周摆放着 $n$ 堆石子，第 $i$ 堆石子的数量为 $a_i$。

现在要将石子有次序地合并成一堆。规定每次只能选择相邻的两堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

请计算将 $n$ 堆石子合并成一堆的最小得分和最大得分。

输入格式

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

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

输出格式

输出两行。

第一行输出最小得分。

第二行输出最大得分。

4
4 5 9 4

43
54

数据范围与提示

• $1 \le n \le 400$
• $0 \le a_i \le 20$

来源

动态规划，区间动归