Hạo và Huy đang chơi một trò chơi trên mảng \(A\) gồm \(n\) phần tử. Cả hai lần lượt thực hiện lượt chơi, bắt đầu từ Hạo:

• Chọn phần tử đầu hoặc phần tử cuối của và xóa nó khỏi mảng. Người chơi được \(x\) điểm với \(x\) là giá trị vừa chọn.

Cho \(x\) và \(y\) lần lượt là số điểm của Hạo và Huy sau khi trò chơi kết thúc. Hạo muốn \(x-y\) là lớn nhất trong khi Huy muốn \(x-y\) là nhỏ nhất.

Giả sử cả hai đều chơi tối ưu, giá trị \(x-y\) khi trò chơi kết thúc là bao nhiêu.

Dữ liệu đầu vào

• Dòng đầu tiên chứa 1 số nguyên \(n\).
• Dòng tiếp theo gồm \(n\) số nguyên \(A_i\)

Dữ liệu ra

• \(x-y\)

Ràng buộc

• \(1 \le n \le 5000\)
• \(1 \le A_i \le 10^9\)

Input 1

4
10 80 90 30

Output 1

10