Семья Вито

Вито хочет переехать на одну длинную улицу. На ней живут $n$ его родственников, дом $i$-го родственника имеет номер $s_i$. Расстояние между двумя домами — модуль разности их номеров.

Вито каждый день навещает всех родственников, поэтому хочет выбрать дом, для которого сумма расстояний до всех родственников минимальна (номер дома — любое целое число). Найдите эту минимальную сумму.

В первой строке $n$ ($1 \le n \le 10^5$). Во второй — $n$ целых чисел $s_1, \ldots, s_n$ ($0 \le s_i \le 10^9$). В одном доме могут жить несколько родственников.

Одно число — минимальная сумма расстояний.

Сумму $|s_1 - x| + \ldots + |s_n - x|$ минимизирует $x$ = медиана (средний элемент отсортированного массива): если $x$ левее медианы, сдвиг вправо уменьшает сумму, если правее — наоборот. При чётном $n$ подходит любое $x$ между двумя средними элементами. В первом примере $x = 4$, ответ $2 + 0 + 2 = 4$.

Сумма достигает $5 \cdot 10^{13}$ — нужен 64-битный тип.

Источник: UVa 10041.