Problem Description

There are $n$ good friends. Each person has a remote-controlled car and a garage. The $i$-th person has several toy road pieces 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 say that the traffic is "connected" if, starting from any garage, it is possible to reach any other garage.

Find the minimum total road length needed to achieve such "connected traffic".

Input Format

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

The second line contains $n$ integers $d_i$, where $d_i$ is the length of the road pieces owned by the $i$-th friend.

Output Format

Output a single line: the minimum total road length needed to achieve "connected traffic".

1
10

0

3
5 5 5

20

4
7 3 3 5

24

Hint

[Explanation for Sample 1]

When there is only one friend, the traffic is already "connected", so there is no need to build any road. Therefore, the answer is $0$.

[Explanation for Sample 3]

If roads are built between friend $1$ and friend $2$, between friend $2$ and friend $3$, and between friend $3$ and friend $4$, a "connected traffic" can be formed. The total cost is $(7+3) + (3+3) + (3+5) = 24$.

[Constraints]

This problem uses bundled subtasks.

• Subtask 1 (10 pts): $d_1 = d_2 = \dots = d_n$.
• Subtask 2 (20 pts): $1 \le n \le 10^3$.
• Subtask 3 (20 pts): No additional constraints.

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

[Hints and Notes]

The scoring of this problem follows the original COCI problem settings, with a full score of $50$.

Translated from COCI2021-2022 CONTEST #4 T1 Autići.

Translated by ChatGPT 5