eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків

Гра

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

На аркуші записано n (2n100, n парне) цілих додатних чисел. Кожне число не перевищує 200. Грають двоє. На кожному ході можна закреслити крайнє число або ліворуч, або праворуч. Закреслене число додадється до очок гравця.

Виведіть максимально можливу суму очок для першого гравця при умові, що супротивник грає найкращим чином.

Вхідні дані

У першому рядку міститься одне ціле число n (2n100, n парне). У наступних n рядках записано вихідний ряд чисел, по одному числу в рядку.

Вихідні дані

Виведіть максимально можливу суму очок для першого гравця при найкращій грі другого гравця.

Приклад

Вхідні дані #1
6
4
7
2
9
5
2

Вихідні дані #1
18