题目描述

在操场上沿直线摆放着 $N$ 堆石子。每次只能选择相邻的两堆合并成新的一堆，本次合并的得分等于两堆石子的总数。经过 $N-1$ 次合并后，所有石子会成为一堆。不同的合并顺序会产生不同总得分，请分别求出最小总得分和最大总得分。

输入格式

第一行输入一个整数 $N$。

第二行输入 $N$ 个整数，第 $i$ 个数表示第 $i$ 堆石子的数量。

输出格式

输出两行。第一行输出最小总得分，第二行输出最大总得分。

数据范围与约定

$2\le N\le300$，$0\le a_i\le1000$。

可见测试数据

输入数据 1

4
4 5 9 4

输出数据 1

44
54

输入数据 2

5
13 13 12 14 4

输出数据 2

130
173

输入数据 3

5
6 18 3 8 18

输出数据 3

117
155