题目描述

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

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

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

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

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

输入格式

第一行包含一个正整数 $n$ —— 表示小朋友的个数。

第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$ —— 表示小朋友们手上的数字，相邻整数之间以一个空格分隔。

输出格式

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

样例输入 1

5
7 5 8 9 3

样例输出 1

111

说明

样例解释

将小朋友安排座位后，从左向右每人手上的数字依次排列为：$9, 8, 7, 5, 3$。

这时可以得到最多的糖果数量：

$(9) + (9 + 8) + (9 + 8 + 7) + (9 + 8 + 7 + 5) + (9 + 8 + 7 + 5 + 3) = 111$。

数据范围

对于所有测试点，保证：

• $1 \le n \le 1000$。
• $1 \le a_i \le 1000$。
• 保证所有的输入数值均为整数。