Problem E: 【GESP5】排排坐

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：4 Solved：2

Description

老师正在和小朋友们分糖果。小朋友们先在的手上写个数字，然后坐成一排。

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

现在小朋友们都已经在手上写上了数字。

请帮小朋友们安排合适的座位顺序，使得小朋友们分到的糖果总量最大，输出这个最大值。


Input

输入共两行行 ，第一行为一个正整数 n ，表明小朋友的个数；
第二行为n 个正整数 p1,p2,...., pn ，表示小朋友们手上的数字，整数之间以空格分隔。

Output

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

Sample Input Copy 

5
7 5 8 9 3

Sample Output Copy 

111

HINT

1≤ n ≤ 1000;    1 ≤ pi≤ 1000 。