时间限制：1秒　　内存限制：256M

---

【问题描述】

　　在一个园形操场的四周摆放 \(N\) 堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

　　试设计出一个算法，计算出将 \(N\) 堆石子合并成一堆的最小得分和最大得分。

【输入格式】

　　第一行试正整数 \(N\)，表示有 \(N\) 堆石子。
　　第二行有 \(N\) 个数，分别表示每堆石子的个数。

【输出格式】

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

【输入输出样例】

　Input

4
4 5 9 4

　Output

43
54

【数据限制】

　　\(1 ≤ N ≤ 100\)，每堆石子的数量不超过 10000。

【来源】

　Mr.he