Гра на максимум суми - підконтрольний суперник
N карток викладено у ряд зліва направо. На кожній картці написане ціле число. Два грвці по черзі забирають по одній картці, причому забирати можна або крайню ліву, або крайню праву. Завершується гра, коли забрано усі картки (доки картки є, гравець зобов'язаний робити один з можливих ходів). Мета гри - отримати якомога більшу суму (чисел, записаних на забраних картках).
Тільки ось "грають" у цю гру незрозуміло навіщо начальник-самодур та підлеглий підлиза. Начальник-самодур може цілком і повністю контролювати не лише свої ходи, але і ходи підлеглого-підлизи. Яку максимальну суму зможе набрати начальник-самодур (який, зрозуміло, ходить першим)?
Вхідні дані
У першому рядку вказано кількість карток N (1 ≤ N ≤ 2013). У другому рядку через пропуски задано N цілих чисел (які не перевищують по модулю 10^3) - значення, записані на картках.
Вихідні дані
Виведіть єдине ціле число - максимальну суму, яку гарантовано може набрати перший гравець (начальник-самодур).
Примітка: Оскільки начальник-самодур повністю контролює ходи підлкглого-підлизи, він може забрати першим ходом 3, наказати "супернику" забирати 1.