На столе в один ряд лежат n монет. На i-й монете указана ценность a_i.

Два игрока по очереди забирают по одной монете. За один ход можно взять только монету с левого конца ряда или с правого конца ряда. Первым ходит первый игрок.

Оба игрока действуют оптимально и стараются максимизировать суммарную ценность монет, которые достанутся именно им.

Требуется определить, какую суммарную ценность наберёт первый игрок к концу игры.

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

Первая строка содержит одно целое число n — количество монет.

Вторая строка содержит n целых чисел a_i — ценности монет в ряду.

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

Выведите одно целое число — максимальную суммарную ценность монет, которую получит первый игрок при оптимальной игре обоих участников.

Ограничения

• 1 <= n <= 1000
• 1 <= a_i <= 10^9

Ответ может не помещаться в 32-битный целочисленный тип.

Примеры

Пример 1

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

1
1

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

1

Пример 2

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

2
1 1000000000

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

1000000000