Cho số nguyên dương n và dãy số nguyên a1, a2, …, an. Tìm giá trị lớn nhất của biểu thức (a[i]+a[j]-a[k]) với 1<=i<j<k<=n).

Input:

• Dòng 1: chứa số n.

• Dòng 2: chứa n số a1, a2, …, an (|ai|<=10^9)

Output

• Ghi ra giá trị lớn nhất của biểu thức.

Sample Input:

7 
8 2 4 -2 9 1 -3

Sample Output:

20

Giới hạn:

Sub1: n≤200 ;   
Sub2: n≤5000;   
Sub3: n≤106