Trò chơi trên mảng

Cho một mảng \(A\) gồm \(n\) số nguyên. Hai người chơi tham gia một trò chơi luân phiên nhau:
Ở mỗi lượt, người chơi hiện tại chọn lấy phần tử ở đầu mảng hoặc phần tử ở cuối mảng, nhận số điểm bằng giá trị của phần tử đó và phần tử đó sẽ bị xóa khỏi mảng.

Trò chơi kết thúc khi mảng không còn phần tử nào. Cả hai người chơi đều chơi tối ưu để tối đa hóa số điểm của mình. Giả sử người thứ nhất đi trước, hãy tính số điểm mà người thứ nhất đạt được khi trò chơi kết thúc.

Input

• Dòng đầu tiên gồm số nguyên \(n\) (\(1 \le n \le 5000\)).

• Dòng tiếp theo gồm \(n\) số nguyên \(A_1, A_2, \ldots, A_n\) (\(1 \le A_i \le 10^9\)).

Output

In ra một số nguyên duy nhất là giá trị \(x - y\).

Example

Input:

4
10 80 90 30

Output:

10