Гра на максимум суми
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.