\(Kaninho\) và \(Henry\) chơi với nhau một trò chơi như sau:

Ban đầu, họ được cho một dãy số \(a=(a_1,a_2,\cdots,a_n)\). Họ lần lượt thực hiện phép toán dưới đây cho đến khi dãy \(a\) rỗng, bắt đầu từ \(Kaninho\):

Loại bỏ phần tử đầu tiên hoặc cuối cùng của dãy \(a\). Người chơi đó sẽ kiếm được \(x\) điểm, với \(x\) là phần tử bị loại bỏ.
Gọi \(X\) và \(Y\) lần lượt là số điểm của \(Kaninho\) và \(Henry\) sau khi trò chơi kết thúc. \(Kaninho\) cố gắng làm \(X−Y\) lớn nhất có thể, trong khi \(Henry\) muốn \(X−Y\) nhỏ nhất có thể.

Giả sử cả hai người đều chơi tối ưu, tìm giá trị của \(X−Y\).

Input

• Dòng thứ nhất chứa số nguyên \(N(1 \leq N \leq 3000)\)
• Dòng thứ hai, chứa \(n\) số nguyên \(a_1,a_2,\cdots,a_n(1 \leq a_i \leq 10^9)\)

Output

• In ra giá trị cần tìm

Example

4
10 80 90 30 

10