Bài toán: Tính điểm tối đa của người chơi đầu tiên

Đề bài

Có một danh sách ~ n ~ số và hai người chơi lần lượt di chuyển. Trong mỗi lượt, một người chơi chọn xóa một số ở đầu hoặc cuối danh sách và cộng giá trị của số đó vào điểm của mình. Cả hai người chơi đều cố gắng tối đa hóa điểm của mình.

Yêu cầu: Tính điểm tối đa của người chơi đầu tiên, với giả định cả hai người đều chơi tối ưu.

Input

• Dòng đầu tiên chứa một số nguyên ~ n ~: số phần tử trong danh sách.
• Dòng thứ hai chứa ~ n ~ số nguyên ~ x_1, x_2, \ldots, x_n ~: nội dung của danh sách.

Output

• Một số nguyên: điểm tối đa của người chơi đầu tiên.

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 đầu tiên chọn ~ 4 ~, sau đó người chơi thứ hai chọn ~ 5 ~, rồi người chơi đầu tiên chọn ~ 3 ~. Điểm của người chơi đầu tiên là ~ 4 + 3 = 8 ~.