题目描述

魔法世界的魔法师曾经因臭氧层破坏而制造出覆盖整个星球大气层,用于抵御超量紫 外线辐射的"天幕"。所以虽然太空防御系统是魔法世界历史上空前绝后的一项超大工程。 但是具体实施起来并不是很困难,它其实是一个围绕整个星球赤道的圆形防御圈,圆形防御 圈四周摆放$\red{N}$堆魔法石$\red{(N≤}$$\red{100) ,}$现要将魔法石有次序地合并成一堆。规定每次只能选相 邻的两堆合并成$\red{-}$堆,并将新的一堆的魔法石数,记为该次合并的得分。编一程序,由文件 读人堆数$\red{N}$及每堆魔法石数$\red{(≤}$$\red{20) ,}$使得:

$\red{(1)}$选择一种合并魔法石的方案,使得做$\red{N-1}$次合并,得分的总和最小;

$\red{(2)}$选择一种合并魔法石的方案,使得做$\red{N-1}$次合并,得分的总和最大。

输入格式

第一行为魔法石堆数$\red{N}$; 第二行为每堆魔法石數.每两个数之间用一空格分隔。

输出格式

两个数，即最大合并数和最小合并数。

样例

输入样例

4
4 5 9 4

输出样例

54 43