Minimum Road Construction for Connected Traffic

There are n friends, each owning a remote-controlled car, a garage, and some toy road pieces. Friend i has a road piece of length \(d_i\). Any two friends \(a\) and \(b\) can build a road connecting their garages with a length equal to \(d_a + d_b\). We say that the traffic is "connected" if any garage can be reached from any other garage.

Your task is to determine the minimum total road length required to achieve connected traffic. Note that if there is only one friend (i.e. \(n=1\)), no road is needed, and the answer is 0.

Hint: By considering the complete graph with edge weights \(d_a+d_b\), the minimum spanning tree (MST) can be attained by connecting every friend, except one with the minimum \(d\), to the friend having the smallest \(d\). The answer is \(\sum_{i=1}^{n} d_i + (n-2) \times \min\{d_i\}\) for \(n \ge 2\).

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), representing the number of friends.

The second line contains n space-separated integers \(d_1, d_2, \ldots, d_n\) where each \(d_i\) represents the length of the toy road piece for friend i.

outputFormat

Output one integer, the minimum total road length required to achieve connected traffic.

sample

1
5

0