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 - a_k~) (~1 \le i < j < k \le N~)

Input

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

Dòng thứ hai gồm ~N~ số nguyên ~a_1,a_2,…,a_N~ (|~a_i~|≤~10^9~)

Output

Kết quả bài toán

Ví dụ:

input

7

8 2 4 -5 9 1 -3

output

20

Giải thích VD

(~i,j,k~)=(~1,5,7~)