该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

车库道路

题目描述

有 $n$ 位小伙伴。每人都有一辆遥控玩具车、一个存放玩具车的车库，以及足够多段用来拼装道路的材料，材料数量不会成为铺路的限制。

第 $i$ 位小伙伴手里的每段材料长度都是 $d_i$。

任意两位不同的小伙伴 $a$ 和 $b$ 都可以各拿出一段材料，把两段材料接起来，在他们的车库之间铺一条道路。因此，这条道路的长度为

请你选择若干对小伙伴来铺设道路，使所有车库连通。也就是说，从任意一个车库出发，都能沿着道路到达其他任意车库。

请计算使所有车库连通所需的最小道路总长度。

输入格式

第一行输入一个整数 $n$（$1\le n\le 100000$），表示小伙伴的数量。

第二行输入 $n$ 个整数 $d_1,d_2,\ldots,d_n$（$1\le d_i\le 10^9$），其中 $d_i$ 表示第 $i$ 位小伙伴手中每段材料的长度。

输出格式

输出一个整数，表示使所有车库连通所需的最小道路总长度。

输入输出样例 #1

输入 #1

1
10

输出 #1

0

输入输出样例 #2

输入 #2

3
5 5 5

输出 #2

20

输入输出样例 #3

输入 #3

4
7 3 3 5

输出 #3

24

说明/提示

样例解释 #1

只有一个车库时，它已经与自身连通，不需要修建道路。

样例解释 #3

可以依次连接小伙伴 $1$ 和 $2$、小伙伴 $2$ 和 $3$、小伙伴 $3$ 和 $4$。总长度为