Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
A new city has been founded! The city has $n$ houses, but no roads yet. The city council hired a construction company to build roads between the houses, so that one can go from any house to another by a road path. The cost of building a road is calculated depending on the value $a$ of each house. The cost of building the road between house $i$ and house $j$, is the absolute value of the difference between their values: $ \left| a_i - a_j \right|$. The council needs to minimize the total cost of building the roads.
Input
First line contains the integer $n$ $(1\le n \le 10^5)$, the amount of houses in the city.
Second line contains $n$ integers separated by spaces $a_1, a_2,..., a_n$ $(1\le a_i\le 10^9)$, the value of each house.
Output
Print on a single line the minimum total cost to connect the houses in the city.