Сумма всех расстояний

Посчитайте сумму $|a_i - a_j|$ по всем парам элементов с разными номерами.

Пар около пяти миллиардов — перебрать их не выйдет.

В первой строке $n$ от $2$ до $10^5$. Во второй — $n$ чисел, каждое по модулю не больше $10^6$.

Одно число.

Отсортируйте. Тогда для каждого $i$ элемент $a_i$ входит в сумму со знаком плюс ровно $i$ раз — по одному за каждый меньший элемент — и вычитается их сумма. Накапливайте эту сумму по ходу прохода. Ответ доходит до $10^{16}$.