H

G. Сизиф

В этой задаче вы будете перекладывать камни. Изначально есть n кучек камней. Кучка i весит a_iкилограммов. Кучки можно объединять. При объединении кучек i и j затрачивается a_i + a_j единиц энергии, при этом две исходные кучки пропадают и появляется кучка весом a_i + a_j.

Определите наименьшее количество энергии, которое надо затратить для объединения всех кучек в одну.

Формат ввода

В первой строке дано число n (1 ≤ n ≤ 10⁵)
В следующей строке записаны массы кучек через пробел — a_i (1 ≤ a_i ≤ 10⁶)

Формат вывода

Выведите единственное число — минимальную энергию, которую надо затратить на объединение всех кучек.

Пример 1

2 2 6

8

Пример 2

3 6 2 4

18