Xét dãy số nguyên ~a_1, a_2, ..., a_n~ và các phép biến đổi có dạng ~C(i, j)~ trên dãy số với ý nghĩa: đổi dấu tất cả các phần tử từ vị trí thứ ~i~ đến vị trí thứ ~j~ (~1 \le i \le j \le n~).

Ví dụ, với dãy ~1, 2, -3, 4, 5, -6~ nếu biến đổi ~C(2, 4)~ ta nhận được dãy ~1, -2, 3, -4, 5, -6~.

Dễ thấy, có tất cả ~\frac{n \times (n+1)}{2}~ phép biến đổi trên dãy gồm ~n~ phần tử. Một phép biến đổi được gọi là tối ưu nếu sau khi thực hiện phép biến đổi ta nhận được dãy có tổng các phần tử là lớn nhất trong tất cả các phép biến đổi.

Yêu cầu: Cho dãy số nguyên ~a_1, a_2, ..., a_n~, hãy tìm phép biến đổi tối ưu.

Input

• Dòng đầu chứa số nguyên dương ~n~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~|a_i| \le 10^9~).

Output

• Gồm một dòng, chứa một số nguyên là tổng các phần tử của dãy sau khi thực hiện phép biến đổi tối ưu.

Sample Input 1

6
1 2 -3 4 5 -6

Sample Output 1

15

Subtasks

• Các test ứng với 40% số điểm có ~n \le 300~.
• Các test khác ứng với 30% số điểm có ~n \le 3000~.
• Các test còn lại ứng với 30% số điểm có ~n \le 300000~.