Гра на максимум суми#5865

Гра на максимум суми

2 секунди

64 мегабайти

Легка

$N$ карток викладено у ряд зліва направо. На кожній картці написано ціле число. Два гравці по черзі беруть по одній картці, причому брати можна або крайню ліву, або крайню праву. Гра завершується, коли взято всі картки (доки картки є, гравець зобов'язаний зробити один з можливих ходів). Мета гри — отримати якнайбільшу суму записаних на взятих картках чисел.

Яку максимальну суму гарантовано зможе набрати перший гравець, незалежно від того, як гратиме другий гравець?

Вхідні дані

У першому рядку вказано кількість карток $N$ ( $1 \leq N \leq 2013$ 1 \le N \le 2013). У другому рядку через пропуски задано $N$ цілих чисел (які не перевищують за модулем $1 0^{3}$ 10^3) — значення, записані на картках.

Вихідні дані

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

Приклади

Приклад 1

Примітка

Якщо на першому ході забрати $1$ , то суперник у відповідь буде змушений забрати або $3$ , або $2$ ; у будь-якому з цих випадків, перший гравець зможе взяти собі $9$ , і таким чином гарантовано отримає суму $10$ (після чого другий гравець забирає останню картку, і гра завершується).

Якби перший гравець на першому ході забрав $3$ , то другий гравець міг би у відповідь забрати $9$ , і у підсумку перший отримав би лише $3 + 2 = 5$ 3 + 2 = 5. Якщо другий гравець відповість на хід «3» ходом «1», перший гравець міг би отримати суму $3 + 9 = 12$ 3 + 9 = 12. Але перший гравець не може гарантувати, що другий зробить настільки невдалий хід, тому відповідь не $12$ , а $10$ .