Có dãy n số nguyên. Hai người luân phiên lấy đúng một số ở đầu trái hoặc đầu phải và cộng vào điểm của mình. Cả hai đều chơi tối ưu.

Yêu cầu

Viết chương trình tính điểm lớn nhất người thứ nhất có thể đảm bảo.

Input

Dòng 1 là n. Dòng 2 gồm n số nguyên ~x_i~.

Output

In điểm tối đa người thứ nhất đạt được khi cả hai chơi tối ưu.

Giới hạn

~1 <= n <= 5000; -10^9 <= x_i <= 10^9~.

Ví dụ input

4
4 5 1 3

Ví dụ output

8

Giải thích ví dụ

Người thứ nhất có chiến lược bảo đảm tổng 8.