Light's Perfect Victory

Light Yagami is pretending to work with the Japanese Task Force in order to uncover the true identity of mass murderer 'Kira' (it's Light). His job is to investigate a given group of suspects, $s$, which is represented by $N$ integers.

Every day, he must split each available group of suspects into two non-empty subgroups so that it seems like he investigated them. However, to avoid skepticism from Ryuzaki, if a group has only $1$ suspect, that group cannot be split further and thus cannot be included in the investigation from the next day onwards.

The value of each suspect still in the investigation is added to the score at the end of each day.

The investigation ends when there are no more groups of suspects left. What is the maximum possible score Light can achieve?

Input

The first line contains a single integer $N$, representing the size of the initial group $s$.

The second line contains $N$ integers $s_1, s_2, \ldots, s_N$, representing the suspects.

Output

A line containing the maximum score achievable.

Constraints

• $1 \le N \le 3 \cdot 10^5$
• $1 \le s_i \le 10^6$ for all $1 \le i \le N$

Example 1

3
8 6 7

36

Explanation

Light initially has the group of suspects $s = [8,6,7]$.

• Light splits it into the two groups $[6]$ and $[8,7]$ for investigation. The score is $21$ at the end of the day, and $[6]$ is discarded.
• Light now has the group $[8,7]$, which he splits into $[8]$ and $[7]$. The score is now $36$ and both groups are no longer part of the investigation.
• There are no more suspects left, so the investigation is complete with a final score of $36$ (which is also the maximum attainable score).

Example 2

5
4 4 1 9 2

69

Example 3

1
1000

1000