Có một danh sách gồm \(n\) số và hai người chơi luân phiên nhau. Tại mỗi lượt, một người chơi loại bỏ đi số đầu tiên hoặc số cuối cùng ra khỏi danh sách, và điểm của người đó tăng thêm một lượng bằng số đó. Cả hai người chơi đều muốn tối đa hóa điểm của họ.

Số điểm tối đa có thể của người chơi thứ nhất là bao nhiêu nếu cả hai người đều chơi tối ưu?

Input

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

Output

• In số điểm tối đa có thể của người chơi thứ nhất.

Constraints

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

Example

Sample input

4
4 5 1 3

Sample output

8