Trò Chơi Loại Bỏ

Hai người chơi thay phiên nhau lấy số từ một danh sách. Mỗi lượt, người chơi chọn lấy số đầu tiên hoặc số cuối cùng của danh sách và cộng vào điểm của mình. Cả hai đều chơi tối ưu để tối đa hóa điểm số của bản thân. Tìm điểm số tối đa mà người chơi đầu tiên có thể đạt được.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $n$: kích thước danh sách.

Dòng thứ hai chứa $n$ số nguyên $x_1,x_2,\dots ,x_n$: các số trong danh sách.

Dữ liệu ra

In ra điểm số tối đa của người chơi đầu tiên.

Ràng buộc

• $1\le n\le 5000$
• $-{10}^9\le x_i\le {10}^9$

Ví dụ