F. Игра финансистов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Эта задача имеет нестандартное ограничение по памяти.

Финансистам Игорю и Жене стало скучно вечером, и они решили сыграть в игру. Для этого они приготовили n ценных бумаг, в которых содержится информация о доходе предприятия за какие-то промежутки времени. Обратите внимание, что доход может быть и положительным, и нулевым, и даже отрицательным.

Игорь и Женя выложили все бумаги в ряд и решили ходить по очереди. Игорь будет брать бумаги слева, а Женя справа. Первым ходит Игорь и берет 1 или 2 по своему выбору ценные бумаги слева. Далее, во время очередного хода игрок может взять k или k + 1 бумагу со своей стороны, если игрок, ходивший перед ним, взял ровно k бумаг. Ход пропускать не может ни один из игроков. Игра заканчивается, когда закончатся бумаги на столе, либо когда игрок не сможет сделать ход.

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

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

В первой строке следует целое положительное число n (1 ≤ n ≤ 4000) — количество бумаг.

Во второй строке следует последовательность из n целых чисел a1, a2, ..., an ( - 105 ≤ ai ≤ 105), где ai равно доходу, информация о котором содержится на i-й бумаге.

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

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

Примеры
Входные данные
3
1 3 1
Выходные данные
4
Входные данные
5
-1 -2 -1 -2 -1
Выходные данные
0
Входные данные
4
-4 -2 4 5
Выходные данные
-13
Примечание

В первом примере Игорю выгодно забрать две бумаги слева, получив суммарный доход 4, тогда Женя не сможет сделать ход, так как осталась всего одна бумага, а он может взять либо 2, либо 3 на текущем ходе.