В некотором королевстве есть N провинций. Король пожелал объединить все их под своей самодержавной властью. Естественно, чтобы никто не догадался об этих планах, он будет это делать поэтапно, а именно: раз в год он будет объединять какие-то две провинции в одну. Чтобы жителям обеих провинций не было обидно, новому территориальному образованию будет присвоено новое название, которое будет отличаться от обоих старых названий. Естественно, это потребует выпуска новых паспортов для жителей обеих провинций. Очевидно, что если в первой провинции жителей, а во второй – жителей, то для них надо выпустить новых паспортов.

На следующий год король объединяет еще какие-то две провинции. И так далее, до тех пор пока вся территория королевства не будет объединена в одну большую «провинцию». Определите, какое наименьшее количество новых паспортов придется выпустить, если король будет объединять провинции оптимально с этой точки зрения.

Формат ввода
В первой строке вводится число N (натуральное, не превышает ) – количество провинций. Затем вводится N чисел – количество жителей каждой провинции (натуральное, не превосходит ). Гарантируется, что изначально в королевстве хотя бы две провинции.

Формат вывода
Выведите единственное число – количество новых паспортов, которые придется выпустить.

Пример 1
Ввод
2
2 6
Вывод
8
Пример 2
Ввод
3
6 2 4
Вывод
18

Siyara1    1   17.10.2020 07:31    131