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

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

Вхідні дані

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

Вихідні дані

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