Description

你和你的伙伴们将礼物都装好了,你们抱着各自的礼物,想通过交换让你们总和的完美值最大。你们的 总和完美值 的计算方法是:每个人的位置*每人礼物的完美值 再求总和。
我们保证每个人手上的完美值都不等。

如下表:

位置 1 2 3 4
所拿礼物的完美值 200 400 100 430
当前的 总和完美值=1*200+2*400+3*100+4*430
现在你们通过两两交换,要使得最终你们的完美值为最大。
如上例子:经过交换后
位置 1 2 3 4
所拿礼物的完美值 100 200 400 430

总和完美值的最大值=1*100+2*200+3*400+4*430
现在要求出最大完美值是多少。另外假设在一个时间单位内,一个人只可以做一次的交换动作(当然也可以原地不动),那么达到最大完美值状态的最短用时是多少。

Input

多组测试数据
对于每个测试数据
第一行:N 表示游戏人数。
第2到N+1行:每行一个数Mi,表示从位置1到位置N,每个人的所拿礼物的完美值。
对于30%的数据N≤10
对于全部的数据N≤10000
对于全部的数据Mi≤100050

Output

第一行:最大完美值
第二行:最小交换所需时间

Sample Input

4
200
400
100
430

Sample Output

3420
2

Source

Jason&&Coolleafly@Hnu