Description

在一圆形操场四周摆放N堆石子 , 现要将石子有次序地合并成一堆.规定每次只能选相临的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分。
编一程序,由文件读入堆数N及每堆石子数,
(1)选择一种合并石子的方案,使得做N-1次合并,得分的总和最少
(2) 选择一种合并石子的方案,使得做N-1次合并,得分的总和最大

Format

Input

第1行：1个整数n(1<=n<=100)，表示石子的数量
第2行：n个用空格分开的整数，每个整数均小于10000，表示各堆石子的数量。

Output

第1行：1个整数，表示最小的归并代价
第2行：1个整数，表示最大的归并代价

Samples

3
13 7 8

43
49

Limitation

1s, 1024KiB for each test case.