该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

在一个圆形操场的四周摆放 N 个马桶，N个神犇分别坐在上面上厕所，现要将神犇有次序地合并成一个.规定每次只能选相邻的 2 个神犇合并成新的一个，新的神犇的尿量则为两个旧神犇尿量的和，并将新的神犇的尿量，记为该次合并的得分。求出将 N 个神犇合并成 1 个的最小和最大的得分总和。

Format

Input

输入第一行为 n ，表示有 n 个神犇
第二行为 n 个用空格隔开的整数，依次表示这 n 神犇的尿量qi。

Output

输出将 N 个神犇合并成 1 个的最小和最大的得分总和。

Sample 1

Input

3
11 45 14

Output

95
129

Limitation

200ms, 2048KiB for each test case.
n <= 100
qi <= 100000000