Олимпиада по программированию для студентов всех курсов 31 марта 2013 г.

Соревнование завершилось 31.03.13 в 16:10

A. Танк

Автор задачи: Пак Александр
Ограничение по времени: 1 с.
Ограничение по памяти: 64 МБ

Есть, значит, Танк. А у Танка система зажигания уж больно мудрая. Система зажигания у него состоит из N лампочек, расположенных в ряд. У каждой лампочки есть своя мощность. Каждая лампочка обладает отдачей при включении, равной сумме мощностей ближайших включенных лампочек слева и справа. Так вот танк, запустится только в том случае, если лампочки включать в такой последовательности, в которой суммарная отдача будет максимально возможной.

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

В первой строке входного потока дано целое число N (1 ≤ N ≤ 16) – количество лампочек. Во второй строке находятся N целых чисел Ai через пробел (-1000 ≤ Ai ≤ 1000) – мощности лампочек.

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

В выходном потоке должно быть одно целое число — максимально возможная отдача.

Примеры
Стандартный вводСтандартный вывод
3
1 2 3
7

Выложен в сеть протокол олимпиады


пояснение к примеру задачи А:

мощности : 1 2 3

1 шаг: _ _ 3 : +0

2 шаг: 1 _ 3 : +3

3 шаг: 1 2 3: +1 +3

итого +7 отдача.


Ошибка в примере. Верные входные данные:

3

1 2 3