Problem Description

There are $n$ friends, each with a remote-controlled car and a garage. The $i$-th friend has several toy road sections of length $d_i$, which can be used to build roads for the cars.

Two friends $a$ and $b$ can build a road of length $d_a + d_b$ to connect their garages.

We consider the situation as "connected traffic" if it is possible to reach any garage from any other garage.

Determine the minimum total road length required to achieve "connected traffic".

Input Format

The first line contains an integer $n$, representing the number of friends.

The second line contains $n$ integers $d_i$, representing the length of the road sections each friend has.

Output Format

Output a single line containing the minimum total road length required to achieve "connected traffic".

Sample Input and Output

Sample Input #1

1
10

Sample Output #1

0

Sample Input #2

3
5 5 5

Sample Output #2

20

Sample Input #3

4
7 3 3 5

Sample Output #3

24

Notes

[Sample 1 Explanation]

When there is only one friend, "connected traffic" is already achieved, so no roads need to be built. Hence, the answer is $0$.

[Sample 3 Explanation]

Building roads between the 1st and 2nd friends, the 2nd and 3rd friends, and the 3rd and 4th friends forms "connected traffic" with a total cost of $(7+3)+(3+3)+(3+5)=24$.

[Data Range and Constraints]

This problem uses subtask-based testing.
- Subtask 1 (10 pts): $d_1 = d_2 = \dots = d_n$.
- Subtask 2 (20 pts): $1 ≤ n ≤ 10^3$.
- Subtask 3 (20 pts): No additional constraints.

For $100\%$ of the data, $1\le n\le10^5, 1\le d_i\le 10^9$.

[Hints and Clarifications]

This problem's scoring is set according to the original COCI contest, with a maximum score of $50$.

The problem is translated from COCI2021-2022 CONTEST #4 T1 Autići.

见题面 Input 部分

见题面 Output 部分