题目描述

在一个圆形操场的四周摆放着 $N$ 堆石子。现在要有次序地把它们合并成一堆，每次只能选择圆环上相邻的两堆合并，并把新一堆的石子数作为本次合并的得分。请计算把 $N$ 堆石子合并成一堆时，可能得到的最小总得分和最大总得分。

输入格式

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

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

输出格式

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

数据范围与约定

$1\le N\le100$，$0\le a_i\le20$。

可见测试数据

输入数据 1

4
4 5 9 4

输出数据 1

43
54

输入数据 2

5
13 13 12 14 4

输出数据 2

129
173

输入数据 3

5
6 18 3 8 18

输出数据 3

117
169