排排坐

题面描述

老师正在和小朋友们分糖果。

小朋友们先在自己的手上写一个数字，然后坐成一排。

老师分发糖果的规则是：每个小朋友获得自己以及左侧所有小朋友的手上数字之和个糖果。

现在小朋友们都已经在自己手上写上了数字。请帮小朋友们安排合适的座位顺序，使得小朋友们分到的糖果总量最大，输出这个最大值。

输入格式

输入共2行：

• 第一行为一个正整数 ，表示小朋友的个数；
• 第二行为 个正整数 ，表示小朋友们手上的数字，整数之间以空格分隔。

输出格式

输出一个整数，表示小朋友们可能分到的最大糖果总数量。

样例1

输入：

5
7 5 8 9 3

输出：

111

样例2

输入：

3
1 2 3

输出：

17

样例解释

对于样例1，小朋友安排座位后从左向右每人手上数字依次是：9、8、7、5、3。

这时可以得到最多的糖果：9 + (9+8) + (9+8+7) + (9+8+7+5) + (9+8+7+5+3) = 9 + 17 + 24 + 29 + 32 = 111。

数据范围

。

时间限制

1.0 s

内存限制

512.0 MB