Cho một dãy số nguyên gồm \(N\) phần tử \(a_1,a_2,…,a_N.\)

Yêu cầu: Tìm giá trị lớn nhất của \((a_j-a_i) với 1≤i<j≤N.\)

Input

• Dòng đầu gồm duy nhất một số nguyên dương \(N (N≤10^6 );\)

• \(N\) dòng tiếp theo mỗi dòng ghi một số nguyên \(a_i (|a_i |≤10^9,1≤i≤N).\)

Output

• Gồm một số là giá trị lớn nhất tìm được.

Ràng buộc:

• Có 50% số test ứng với 50% số điểm thoả mãn: \(1≤N≤10^3; \)

• Có 50% số test còn lại ứng với 50% số điểm thoả mãn: \(10^3<N≤10^5.\)

Sample Input

7
8
2
4
-2
9
1
-3

Sample Output

11