J - Joining Cities

Time limit: 1 s
Memory limit: 1024 MiB
Languages: C, C++, Java, Python, ... (details)

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.

Sample test(s)

Input
2 1 1
Output
0
Input
5 10 10 9 2 3
Output
8
Input
9 8 12 4 10 11 1 2 5 5
Output
11