Максимальная сумма

Пусть {a₁, a₂, a₃, …, a_N} – список натуральных чисел, где N – количество элементов списка.

У нас есть следующий алгоритм:

1. Расположить числа в определенном порядке по кругу.
2. Удалить одно число из круга.
3. Если в круге осталось два числа, тогда посчитать их сумму и она станет результатом работы алгоритма, иначе заменить текущий список {b₁, b₂, b₃, …, b_k-1, b_k} на список {b₁ + b₂, b₂ + b₃, …, b_k-1 + b_k, b_k + b₁} и перейти к пункту 2.

Какую максимальную сумму можно получить в результате работы алгоритма?

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

Входной файл INPUT.TXT содержит в первой строке натуральное число N. Во второй строке N натуральных чисел a_i через пробел. (3 ≤ N ≤ 10³; 1 ≤ a_i ≤ 10⁶).

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

В выходной файл OUTPUT.TXT выведите ответ на задачу.

Пример

Автор задачи

Владимир Игоревич Лукьянчиков

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]