Vito's family

Vito wants to move to a long street where $n$ of his relatives live; the house of the $i$-th relative has number $s_i$. The distance between two houses is the absolute difference of their numbers.

Vito visits all his relatives every day, so he wants to choose a house that minimises the sum of distances to all relatives (the house number can be any integer). Find this minimum sum.

The first line contains $n$ ($1 \le n \le 10^5$). The second line contains $n$ integers $s_1, \ldots, s_n$ ($0 \le s_i \le 10^9$). Several relatives may live in the same house.

A single number — the minimum sum of distances.

The sum $|s_1 - x| + \ldots + |s_n - x|$ is minimised by $x$ = the median (the middle element of the sorted array): if $x$ is left of the median, moving it right decreases the sum, and vice versa. For even $n$ any $x$ between the two middle elements works. In the first example $x = 4$ and the answer is $2 + 0 + 2 = 4$.

The sum reaches $5 \cdot 10^{13}$ — a 64-bit type is needed.

Source: UVa 10041.