Statement is not available in English language
K. День маринованного огурца
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

14 ноября в США отмечается День маринованного огурца.

Вы приехали в город, где каждый год устраивают ярмарку в честь этого прекрасного праздника. Там вы решили поучаствовать в соревновании по опустошению банок с огурцами.

Перед вами на столе стоят $$$n$$$ банок. В $$$i$$$-й банке изначально лежит $$$a_i$$$ огурцов.

За один ход вы выбираете одну непустую банку и вынимаете из неё от одного до всех оставшихся в ней огурцов. Жюри начисляет по одному штрафному баллу за каждый огурец, вынутый на этом ходу, и по одному за каждый огурец во всех остальных банках.

Пустые банки сразу убирают со стола. Соревнование заканчивается, когда на столе не остаётся банок. Какое минимальное суммарное количество штрафных баллов вы можете набрать?

Входные данные

В первой строке дано целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество банок.

Во второй строке даны $$$n$$$ целых чисел $$$a_1,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — начальное количество огурцов в каждой банке.

Выходные данные

Выведите одно целое число — минимальное суммарное количество штрафных баллов.

Примеры
Входные данные
4
3 1 4 2
Выходные данные
20
Входные данные
1
7
Выходные данные
7
Входные данные
3
2 2 2
Выходные данные
12
Примечание

В первом примере можно опустошить третью банку, затем первую, четвёртую и вторую. Штрафы за эти ходы равны соответственно $$$10$$$, $$$6$$$, $$$3$$$ и $$$1$$$.

Если на первом ходу вынуть один огурец из банки с четырьмя, штраф составит $$$1 + (3 + 1 + 2) = 7$$$ баллов. Первое слагаемое соответствует вынутому огурцу, а сумма в скобках — огурцам в остальных банках.

Во втором примере можно опустошить единственную банку за один ход и получить $$$7$$$ баллов. В третьем примере можно опустошать банки целиком в любом порядке, получая $$$6$$$, $$$4$$$ и $$$2$$$ балла.