Інвертування Гаффмана
Статичне кодування Хаффмана — це алгоритм, що використовується переважно для стиснення тексту. Дано текст, що складається з N різних символів, і алгоритм обирає N кодів, по одному для кожного символу. Текст стискається за допомогою цих кодів. Для вибору кодів алгоритм будує двійкове кореневе дерево з N листками. Для N ≥ 2 дерево можна побудувати наступним чином:
Для кожного символу в тексті створіть дерево з одним вузлом і призначте йому вагу, що дорівнює кількості появ символу в тексті.
Створіть множину s, що містить ці N дерев.
Поки s містить більше одного дерева:
(a) Оберіть t_1 з мінімальною вагою з s і видаліть його.
(b) Оберіть t_2 з мінімальною вагою з s і видаліть його.
(c) Створіть нове дерево t з t_1 як лівим піддеревом і t_2 як правим піддеревом, і призначте t суму ваг t_1 та t_2.
(d) Додайте t у s.
Поверніть єдине дерево, що залишилося в s.
Для тексту "abracadabra", дерево, створене за цією процедурою, може виглядати як те, що зображено зліва на наступному малюнку, де кожен внутрішній вузол позначений вагою піддерева, що вкорінене в цьому вузлі. Зверніть увагу, що отримане дерево може також виглядати як те, що справа на малюнку, оскільки на кроках 3(a) та 3(b) множина s може містити кілька дерев з мінімальною вагою.
Для кожного символу в тексті його код визначається шляхом у кінцевому дереві від кореня до листка, що відповідає символу. Довжина коду — це кількість ребер на цьому шляху (що дорівнює кількості внутрішніх вузлів на шляху). Припускаючи, що дерево зліва було побудоване алгоритмом, код для "r" має довжину 3, тоді як код для "d" має довжину 4.
Ваше завдання — за заданими довжинами N кодів, обраних алгоритмом, знайти мінімальний розмір (загальну кількість символів), який може мати текст, щоб згенеровані коди мали ці N довжини.
Вхідні дані
Перший рядок містить ціле число N (2 ≤ N ≤ 50), що представляє кількість різних символів у тексті. Другий рядок містить N цілих чисел L_i, що вказують довжини кодів, обраних алгоритмом Хаффмана для різних символів (1 ≤ L_i ≤ 50 для i = 1, 2, ..., N). Ви можете припустити, що існує принаймні одне дерево, побудоване, як описано, що продукує коди з даними довжинами.
Вихідні дані
Виведіть одне ціле число, що представляє мінімальний розмір (загальну кількість символів), який може мати текст, щоб згенеровані коди мали дані довжини.