有 $n$ 位朋友。每位朋友都有一辆遥控玩具车和一个存放该车的车库。每位朋友还拥有一包用于建造赛道的道路部件。第 $i$ 位朋友包中的所有道路部件长度均为 $d_i$。
两位不同的朋友 $a$ 和 $b$ 可以用一条道路连接他们的车库。为了建造这条道路，他们每人都会从自己的包中取出一个道路部件并将它们连接起来，从而获得一条长度为 $d_a + d_b$ 的道路。一些朋友将以这种方式连接他们的车库，使得所有人的车库都连通。换句话说，从任何一个车库出发，都应该能够通过道路到达任何其他车库。
请问要使所有车库连通，所需的道路总长度最小是多少？
输入格式
第一行包含一个正整数 $n$ ($1 \le n \le 100\,000$)，表示朋友的数量。 第二行包含 $n$ 个正整数 $d_i$ ($1 \le d_i \le 10^9$)，表示第 $i$ 位朋友包中道路部件的长度。
输出格式
仅输出一行，表示使所有车库连通所需的最小道路总长度。
子任务
| 子任务 | 分值 | 约束条件 |
|---|---|---|
| 1 | 10 | $d_1 = d_2 = \dots = d_n$ |
| 2 | 20 | $1 \le n \le 1000$ |
| 3 | 20 | 无附加约束 |
样例
输入格式 1
1 10
输出格式 1
0
说明
由于只有一位朋友，他的车库本身就是连通的，因此不需要建造任何道路。
输入格式 2
3 5 5 5
输出格式 2
20
输入格式 3
4 7 3 3 5
输出格式 3
24
说明
如果分别在朋友 1 和 2、2 和 3、以及 3 和 4 之间建造道路，所有人都会连通，总成本为 $(7 + 3) + (3 + 3) + (3 + 5) = 24$。