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

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

Вхідні дані

У першому рядку вказано кількість карток ~N~ (~1\leqslant N\leqslant 2013~). У другому рядку через пробіли задані ~N~ цілих чисел (що не перевершають за модулем ~10^3~; інакше кажучи, належать проміжку ~[-1000; +1000]~) – значення, записані на картках.

Вихідні дані

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

Приклади

Ввід

4
1 2 9 3

Вивід

10

Примітки

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

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