Bờm có một mảng ~a_1, a_2, \dots, a_n~. Anh được phép thực hiện nhiều nhất một thao tác (cũng có thể không làm gì) như sau: chọn hai chỉ số ~l~, ~r~ với ~1 \le l \le r \le n~ rồi đổi dấu mọi phần tử ~a_l, a_{l+1}, \dots, a_r~.

Chẳng hạn, với ~n = 5~, mảng ~[1, -2, 0, 3, -1]~, chọn ~l = 2~, ~r = 4~ thì mảng trở thành ~[1, 2, 0, -3, -1]~.

Hãy tìm tổng các phần tử lớn nhất có thể có của mảng sau khi thực hiện tối đa một thao tác như vậy.

Dữ liệu

• Dòng đầu chứa số nguyên dương ~n~ (~1 \le n \le 2 \times 10^5~), độ dài của mảng ~a~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~|a_i| \le 10^9~).

Kết quả

• In ra một số nguyên: tổng lớn nhất đạt được sau khi thực hiện nhiều nhất một thao tác.

Ví dụ

SUMMAX.INP

6
-1 7 -4 -2 5 -8

SUMMAX.OUT

15

Giải thích: Đổi dấu đoạn ~[-4, -2, 5, -8]~ thành ~[4, 2, -5, 8]~, mảng mới là ~[-1, 7, 4, 2, -5, 8]~ có tổng 15.

Giới hạn

• Subtask 1 (50% số điểm): ~n \le 1000~.
• Subtask 2 (50% số điểm): không có ràng buộc gì thêm.