Игра на максимум суммы
N карточек выложены в ряд слева направо. На каждой карточке написано целое число. Два игрока поочередно забирают по одной карточке, причем забирать можно либо крайнюю левую, либо крайнюю правую. Заканчивается игра, когда забраны все карточки (пока карточки есть, игрок обязан делать один из возможных ходов). Цель игры - получить как можно большую сумму (чисел, записанных на забранных карточках).
Какую максимальную сумму гарантированно сможет забрать первый игрок?
Входные данные
В первой строке указано количество карточек N (1 ≤ N ≤ 2013). Во второй строке через пробелы заданы N целых чисел (не превосходящих по модулю 10^3) - значения, записанные на карточках.
Выходные данные
Выведите единственное целое число - максимальную сумму , которую гарантированно может набрать первый игрок.
Примечание: Если на первом ходу забрать 1, то соперник в ответ будет вынужден забрать либо 3, либо 2; в любом из этих случаев, первый игрок сможет забрать себе 9, и, таким образом, гарантированно получить сумму 10 (после чего второй игрок забирает последнюю карточку, и игра заканчивается).
Если бы первый игрок на первом ходу забирал 3, то второй игрок мог бы в ответ забрать 9, и в итоге первый получил бы всего лишь 3+2=5. При большой глупости, второй игрок мог бы ответить на ход "3" и ходом "1"; в этом случае первый игрок мог бы получить сумму 3+9=12. Но первый игрок не может гарантировать, что второй сделает столь глупый ход, потому и ответ не 12, а 10.