Cho dãy số nguyên ~a~ độ dài ~n~, bạn phải lần lượt thực hiện thao tác đúng ~2~ lần, mỗi thao tác bao gồm ~2~ bước sau:

• Chọn ~2~ giá trị ~l~, ~r~ sao cho ~1 \leq l \leq r \leq n~.

• Đổi dấu các phần tử trong đoạn từ ~l~ đến ~r~ của dãy ~a~. Nói cách khác, gán ~a[i] = -a[i]~ với mọi ~l \leq i \leq r~.

Hãy tìm cách thực hiện đúng ~2~ thao tác sao cho sau khi thực hiện, tổng các phần tử dãy ~a~ là lớn nhất có thể.

Input

• Dòng đầu tiên chứa số nguyên ~n~ là độ dài của dãy ~a~ (~n \leq 10^5~).

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, a_3,..., a_n~ là các phần tử của dãy ~a~ (~-10^9 \leq a_i \leq 10^9~)

Output

Một số nguyên duy nhất là kết quả bài toán.

Scoring

• Subtask 1 (~20~ điểm): ~n \leq 100~.

• Subtask 2 (~30~ điểm): ~n \leq 1000~.

• Subtask 3 (~50~ điểm): không có ràng buộc gì thêm.

Sample Input 1

4
-1 2 -3 -4

Sample Output 1

10