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$$$) — начальное количество огурцов в каждой банке.
Выведите одно целое число — минимальное суммарное количество штрафных баллов.
43 1 4 2
20
17
7
32 2 2
12
В первом примере можно опустошить третью банку, затем первую, четвёртую и вторую. Штрафы за эти ходы равны соответственно $$$10$$$, $$$6$$$, $$$3$$$ и $$$1$$$.
Если на первом ходу вынуть один огурец из банки с четырьмя, штраф составит $$$1 + (3 + 1 + 2) = 7$$$ баллов. Первое слагаемое соответствует вынутому огурцу, а сумма в скобках — огурцам в остальных банках.
Во втором примере можно опустошить единственную банку за один ход и получить $$$7$$$ баллов. В третьем примере можно опустошать банки целиком в любом порядке, получая $$$6$$$, $$$4$$$ и $$$2$$$ балла.
| Name |
|---|


