题目描述

在一个圆形操场的四周摆放有 $N$ 堆石子（$N \le 500$）。现要将这些石子按照某种顺序合并成一堆。

每次操作只能选择相邻的两堆合并成新的石子堆，并将这两堆石子数之和作为该次合并的得分。

给定每堆石子的数量（每堆 $\le 20$），需要求：

1. 最小总得分：选择一种合并方案，使得经过 $N-1$ 次合并后，总得分最小。
2. 最大总得分：选择一种合并方案，使得经过 $N-1$ 次合并后，总得分最大。

注意：由于石子堆是环形摆放的，首尾视为相邻。

输入格式

第一行输入整数 $N$，表示石子堆数量。

第二行输入 $N$ 个整数，表示从最上面一堆起，顺时针方向的石子数量。

输出格式

输出两行：

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

输入输出样例 #1

输入 #1

4
4 5 9 4

输出 #1

43
54

说明/提示

数据范围

• $1 \le N \le 500$
• 每堆石子数量 $\le 20$