Background

经典石子合并问题

Description

有N堆石子排成一排(n<=100),现要将石子有次序地合并成一堆，规定每次只能选相邻的两堆合并成一堆，并将新的一堆的石子数，记为改次合并的得分，编一程序，由文件读入堆数n及每堆石子(<=200)； （1）选择一种合并石子的方案，使得做n-1次合并，得分的总和最少 （2）选择一种合并石子的方案，使得做n-1次合并，得分的总和最多

Format

Input

第一行为石子堆数n 第二行为每堆石子数，每两个数之间用一空格分隔。

Output

第一行为合并得分的最小值 第二行为合并得分的最大值

Sample 1

Input

4
4 5 9 4

Output

44
54

Limitation

1s, 1024KiB for each test case.