Player-based Team Distribution

Interview

Time limit1sMemory limit1024 MB

Summary

Partition N players into teams; a player with value a_i in a team of size s scores s*a_i. Maximize the total score.

Level: Medium4 of 10
Topics: Greedy, Sorting, Math, Implementation
Solved: No attempts yet

Problem

We want to split $N$ players into one or more teams and play a game. Each player must belong to exactly one team. The $i$ -th player gains a score equal to the number of players on the same team multiplied by $a_i$ .

Find the maximum possible sum of all players' scores over all ways to split the players into teams.

Input

The first line contains $N$ . ( $1 \leq N \leq 10^5$ )

The second line contains $N$ integers. The $i$ -th number is $a_i$ . ( $-10^5 \leq a_i \leq 10^5$ )

Output

Print on the first line the maximum sum of all players' scores over all ways to split the players into teams.

Examples1

Example 1
Input
```
4
2 3 -4 1
```
Expected output
```
14
```