Trò chơi loại bỏ

Trong một buổi thảo luận về chiến lược truyền thông, FullHouse Dev được đưa ra một bài toán thú vị về việc tối ưu hóa điểm số. Họ nhận thấy bài toán này tương tự như cách xây dựng chiến lược truyền thông: đôi khi cần phải đưa ra những quyết định khôn ngoan giữa các lựa chọn trước mắt và lâu dài.

Bài toán

FullHouse Dev có một danh sách \(n\) số và hai người chơi lần lượt thực hiện các bước đi. Trong mỗi lượt, người chơi phải loại bỏ số đầu tiên hoặc số cuối cùng của danh sách, và điểm số của họ sẽ tăng thêm giá trị của số đó. Cả hai người chơi đều cố gắng tối đa hóa điểm số của mình. Nhiệm vụ là tìm ra điểm số cao nhất có thể đạt được cho người chơi thứ nhất khi cả hai người đều chơi tối ưu.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(n\): kích thước của danh sách.
• Dòng tiếp theo chứa \(n\) số nguyên \(x_1, x_2, ..., x_n\): nội dung của danh sách.

OUTPUT FORMAT:

• In ra điểm số cao nhất có thể đạt được cho người chơi thứ nhất.

Ràng buộc:

• \(1 \leq n \leq 5000\)
• \(-10^9 \leq x_i \leq 10^9\)

Ví dụ

INPUT

4
4 5 1 3

OUTPUT

8

Giải thích

Người chơi thứ nhất có thể đạt được điểm số tối đa là 8 bằng cách:

• Lượt 1: Chọn số 4 ở đầu danh sách (điểm: 4)
• Lượt 2: Người chơi thứ hai chọn số 5
• Lượt 3: Chọn số 3 ở cuối danh sách (điểm thêm: 4 + 3 = 8)
• Lượt 4: Người chơi thứ hai buộc phải chọn số 1 Tổng điểm của người chơi thứ nhất là 8.