Cho trước một dãy số nguyên A=a1,a2,...,an. Gọi Sum(L,R) là tổng các phần tử thuộc dãy con từ chỉ số L đến R-1. Ví dụ: Với A=(3,-4,1,6) thì: Sum(1,2)=3; Sum(1,3)=-1; Sum(1,5)=6; An muốn dùng 3 chỉ số x1,x2,x3 (1≤x1≤x2≤x3≤n+1) để chia dãy A thành các dãy con sao cho: Res=Sum(1,x1)–Sum(x1,x2)+Sum(x2,x3)–Sum(x3,n+1) đạt lớn nhất.

Dữ liệu vào:

• Dòng đầu tiên ghi số nguyên n (1≤n≤〖10〗^5)

• Dòng thứ hai ghi n số nguyên a1,a2,...,an (|ai |≤〖10〗^9)

Kết quả:

gồm một số nguyên cho biết giá trị Res lớn nhất có thể.

Sample Input

5
2 8 -1 7 -2

Sample Output

20

Ràng buộc:

- 30% số test tương ứng 30% số điểm có n≤300
- 30% số test khác tương ứng 30% số điểm có 300<n≤5000
- 40% số test còn lại tương ứng 40% số điểm có n≤〖10〗^5