题目描述

有 $n$ 堆石子围成一个圆环。每次只能合并相邻的两堆，得分为合并后这堆石子的数量。进行 $n-1$ 次合并后只剩一堆。分别求总得分的最小值和最大值。

输入格式

第一行整数 $n$。第二行按环上顺序给出 $n$ 堆石子的数量。

输出格式

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

样例

4
4 5 9 4

43
54

数据范围

$1\le n\le100$，$1\le a_i\le20$。