Cho số nguyên \(n\) và dãy số nguyên \(a_1,a_2,…,a_n.\) Chỉ được phép tối đa 1 phép biến đổi trong mảng đó là chọn 2 số \((i,j) \) và đổi dấu tất cả các phần tử \(a_i,a_{i+1},…,a_j.\)

Yêu cầu: Tính tổng lớn nhất có thể của dãy nếu được phép thực hiện tối đa 1 lần biến đổi trong dãy.

Input

• Dòng thứ nhất chứa hai số nguyên \(n (1≤n≤2*10^5 ).\)

• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,…,a_n (|a_i |≤10^9 ).\)

Output

• Ghi tổng lớn nhất có thể tìm được.

Ràng buộc

• Subtask 1: \(n≤10^3.\)

• Subtask 2: \(n≤2*10^5.\)

Sample Input

6
-1 7 -4 -2 5 -8

Sample Output

15