Có một dãy 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, \ldots, x_n\): các phần tử của dãy.

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