Trò chơi lấy hai đầu

An và Bình chơi một trò chơi trên dãy số nguyên dương \(a_1, a_2, \dots, a_n\). Hai người lần lượt chơi, An đi trước. Ở mỗi lượt, người chơi phải lấy đi phần tử ở đầu trái hoặc đầu phải của dãy hiện tại và cộng giá trị phần tử đó vào điểm của mình. Trò chơi kết thúc khi dãy hết phần tử.

Gọi \(X\) và \(Y\) là tổng điểm cuối cùng của An và Bình. An muốn \(X - Y\) càng lớn càng tốt, còn Bình muốn \(X - Y\) càng nhỏ càng tốt. Cả hai đều chơi tối ưu.

Hãy in ra giá trị \(X - Y\) khi kết thúc trò chơi.

Input

• Dòng đầu tiên chứa số nguyên \(n\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\).

Output

In ra một số nguyên là giá trị \(X - Y\) (có thể âm).

Constraints

• \(1 \le n \le 3000\)
• \(1 \le a_i \le 10^9\)

Sample Input

5
6 2 9 4 7

Sample Output

-2

Explanation

Tổng các phần tử là \(28\). Khi cả hai chơi tối ưu, An thu được \(13\) điểm và Bình thu được \(15\) điểm nên \(X - Y = -2\).