Добавить все

Лимит времени 2 секунды

Лимит использования памяти 128 MiB

Стоимость сложения двух чисел положим равным их сумме. Например, сложить числа 1 и 10 стоит 11. Стоимость сложения 1, 2 равна 3. Складывать числа можно разными способами:

1 + 2 = 3 (стоимость = 3), 3 + 3 = 6 (стоимость = 6). Всего = 9
1 + 3 = 4 (стоимость = 4), 2 + 4 = 6 (стоимость = 6). Всего = 10
2 + 3 = 5 (стоимость = 5), 1 + 5 = 6 (стоимость = 6). Всего = 11

Надеемся, Вы поняли Вашу задачу. Вам необходимо сложить все числа так, чтобы суммарная стоимость их сложения была наименьшая.

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

Первая строка содержит натуральное число n (2 ≤ n ≤ 10^5). Вторая строка содержит n целых неотрицательных чисел, каждое из которых не больше 10^5.

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

Вывести наименьшую стоимость сложения всех чисел.

Пример

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

3
1 2 3

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