Biến đổi dãy số

Xét dãy số nguyên $a_1,a_2,\dots ,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. Phải thực hiện đúng một phép biến đổi, tức là luôn có ít nhất một phần tử bị đổi dấu.

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

Dữ liệu vào

• 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,\dots ,a_n$ ($|a_i|\le {10}^9$).

Dữ liệu ra

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.

Ràng buộc

• $1\le n\le 300000$.
• $|a_i|\le {10}^9$.

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$.

Ví dụ