На аркуші паперу в ряд записано \(N\) натуральних чисел.
Грає два гравця. За кожен хід можна викреслити крайнє число зліва або справа. Закреслене число додається до балів гравця.
Гру починає перший гравець. Визначіть, яку найбільшу суму він може набрати, за умови, що суперник грає найкращим чином.

Формат вхідних даних

Число \(N\) (\(2 \le N \le 1000\)). Число \(N\) парне.
В наступному рядку \(N\) чисел \(Ci\), які виписані на папері. (\(1 \le Ci \le 1000\))

Формат вихідних даних

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

Приклад вхідних даних

6
4 7 2 9 5 2

Приклад вихідних даних

18