Ami có một dãy \(A\) gồm \(N\) số nguyên. Định nghĩa \(f(l, r) = a[l] + a[l+1] + \dots + a[r] + \max(a[l], a[l+1], \dots, a[r]) - \min(a[l], a[l+1], \dots, a[r])\). Hãy tìm \(f(l, r)\) lớn nhất của dãy \(A\).

Input

• Dòng đầu tiên chứa một số nguyên dương \(N \le 10^5\) là số lượng phần tử của dãy \(A\).
• \(N\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(A[i]\) (\(|A[i]| \le 10^9\)), là một phần tử của dãy \(A\).

Output

• Một dòng duy nhất là giá trị \(f(l, r)\) lớn nhất tìm được.

Example

3
1
2
3

8

2
-1
-2

-1