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

Після закінчення гри підраховується \(X\) - сума чисел які взяв Назар, \(Y\) - сума чисел які взяла Марійка.

Назар грає оптимально так, щоб максимізувати значення \(X-Y\), а Марійка грає оптимально, щоб мінімізувати значення \(X-Y\)

Знайдіть результуюче значення \(X-Y\) якщо перший хід робить Назар.

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

В першому рядку ціле число \(N\) (\(1 \le N \le 3000\))
В наступому рядку \(N\) цілих чисел \(Ai\) - (\(1 \le Ai \le 10^9\))

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

Виведіть значення \(X-Y\) якщо обидва гравці грають оптимально, і першим ходить Назар.

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

4
10 80 90 30

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

10

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

3
10 100 10

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

-80

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

1
10

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

10

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

10
1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1

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

4999999995

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

6
4 2 9 7 1 5

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

2