题目内容

有 $n$ 堆石子围成一圈，第 $i$ 堆有 $a_i$ 颗石子。每次把相邻的两堆合并成一堆，新堆的石子数等于原来两堆之和，这一次的代价也等于这个和。因为是一圈，第一堆和最后一堆也算相邻。把 $n$ 堆合成一堆一共要合并 $n-1$ 次。请输出所有合并顺序里，总代价的最小值和最大值。

只有一堆时不用合并，最小值和最大值都是 $0$。

输入描述

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

约束

$1 \le n \le 200$

$1 \le a_i \le 10^6$

输出描述

输出两个整数，依次是最小总代价和最大总代价，中间用空格隔开。

样例1

输入

4
4 5 9 4

输出

43 54

说明

最小的一种：先把首尾两个 $4$ 合并，代价 $8$，再和 $5$ 合并，代价 $13$，最后和 $9$ 合并，代价 $22$。总代价 $8+13+22=43$。

最大的一种：先合并 $5$ 和 $9$，代价 $14$，再和旁边的 $4$ 合并，代价 $18$，最后和剩下的 $4$ 合并，代价 $22$。总代价 $14+18+22=54$。

样例2

输入

1
1000000

输出

0 0

说明

只有一堆，没有合并，代价是 $0$。

样例3

输入

2
3 8

输出

11 11

说明

两堆只能合并一次，代价就是 $3+8=11$，最小值和最大值相同。