Problem Description

The teacher is giving candies to children.

Each child first writes a number on their hand, then sits in a row.

The rule for giving candies is: each child gets a number of candies equal to the sum of the numbers on their own hand and on the hands of all children to their left.

Now all children have already written their numbers.

Please help the children arrange a suitable seating order so that the total number of candies they receive is as large as possible, and output this maximum value.

Input Format

The input has $2$ lines.

The first line contains a positive integer $n$, representing the number of children.

The second line contains $n$ positive integers $a_1, a_2, \cdots, a_n$, representing the numbers on the children’s hands. The integers are separated by spaces.

Output Format

Output one integer, representing the maximum total number of candies the children can receive.

5
7 5 8 9 3

111

Hint

Sample Explanation

After arranging the seats, from left to right the numbers on the children’s hands are: $9, 8, 7, 5, 3$.

Then the maximum number of candies can be obtained: $(9) + (9 + 8) + (9 + 8 + 7) + (9 + 8 + 7 + 5) + (9 + 8 + 7 + 5 + 3) = 111$.

Constraints

$1 \le n \le 1000$，$1 \le a_i \le 1000$。

Translated by ChatGPT 5