D. Коробки и шары
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Ивана есть n различных коробок. В первой из них лежат шары n различных цветов.

Иван планирует организовать следующую игру. Он хочет распределить шары по коробкам таким образом, чтобы для любого i (1 ≤ i ≤ n) i-я коробка содержала все шары цвета i.

Иван совершит некоторые ходы, чтобы добиться этого. В каждый ход он делает следующие шаги:

  1. Иван выбирает любую непустую коробку и вытаскивает все шары из нее;
  2. Потом Иван выбирает любые k пустых коробок (коробка из первого шага стала пустой, Иван может выбрать и ее), разделяет шары с предыдущего шага на k непустых групп и помещает каждую из групп в одну их этих коробок. Он обязан положить каждую группу шаров в отдельную коробку. Он может выбрать только k = 2 или k = 3.

За ход Ивану добавляется штраф, равный количеству шаров, которые он вытащил на первом шаге. Штраф за игру считается, как сумма штрафов за ходы, которые Иван совершил до распределения всех шаров по соответствующим коробкам.

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

В первой строке записано одно целое число n (1 ≤ n ≤ 200000) — количество коробок и цветов.

Во второй строке записаны n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109), где ai — количество шаров цвета i.

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

Выведите одно число — минимальный возможный штраф за игру.

Примеры
Входные данные
3
1 2 3
Выходные данные
6
Входные данные
4
2 3 4 5
Выходные данные
19
Примечание

В первом примере стоит вытащить все шары из первой коробки, выбрать k = 3 и распределить все цвета по соответствующим коробкам. Штраф — 6.

Во втором примере надо сделать два хода:

  1. Взять все шары из первой коробки, выбрать k = 3, положить шары цвета 3 в третью коробку, цвета 4 — в четвертую коробку, а остальные вернуть в первую коробку. Штраф — 14;
  2. Взять все шары из первой коробки, выбрать k = 2, положить шары цвета 1 в первую коробку, а шары цвета 2 — во вторую коробку. Штраф — 5.

Суммарный штраф — 19.