Сумма максимумов по парам

Для каждой пары элементов с разными номерами возьмите больший из двух и сложите все эти значения.

Если элементы равны, берётся само это значение.

В первой строке $n$ от $2$ до $10^5$. Во второй — $n$ чисел от $0$ до $10^6$.

Одно число.

После сортировки элемент $a_i$ оказывается максимумом ровно в $i$ парах — по одной с каждым, кто стоит левее. Дальше это одна строка. Ответ доходит до $5 \cdot 10^{15}$.