Є список з ~n~ чисел і два гравці, які ходять по черзі. Під час кожного ходу гравець видаляє перше або останнє число зі списку, і його рахунок збільшується на це число. Обидва гравці намагаються максимізувати свої результати.

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

Обмеження

• ~1 \le n \le 5000~
• ~-10^9 \le x_i \le 10^9~

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

Перший рядок містить ціле число ~n~: розмір списку.

Наступний рядок містить ~n~ цілих чисел ~x_1,x_2,\ldots,x_n~: вміст списку.

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

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

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

4
4 5 1 3

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

8