Xét dãy số nguyên a₁, a₂,.., 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<= i<= j<= 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ả (n.(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₁, a₂,.., a_n, hãy tìm phép biến đổi tối ưu  

Dữ liệu vào: Vào từ file văn bản CSEQ.INP gồm:

• Dòng đầu chứa số nguyên dương n (n<= 3.10⁵);
• Dòng thứ hai chứa n số nguyên a₁, a₂,.., a_n (|a_i|<= 10⁹).

Dữ liệu ra: Ghi ra file văn bản CSEQ.OUT gồm một số nguyên duy nhất 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.