Lưu ý: Bài làm được chấm bằng bộ test tự sinh của CLAOJ.

Trong giờ Tin Học, hai bạn học sinh Linh và Trung rủ nhau chơi một trò chơi với dãy số nguyên ~A~ gồm ~N~ phần tử. Hai bạn sẽ thay phiên nhau, mỗi người chơi ở một lượt. Ở mỗi lượt chơi, các bạn sẽ thực hiện như sau:

• Chọn một đoạn bất kỳ trong dãy ~A~ từ vị trí ~L~ đến ~R~ (với ~1 \leq L \leq R \leq N~).
• Đổi dấu các phẩn tử từ ~L~ đến ~R~ của dãy ~A~ (gán ~a[i] = -a[i]~ với mọi ~L \leq i \leq R~).

Mục tiêu cuối cùng là tổng các phần tử trong dãy ~A~ lớn nhất có thể sau hai lượt chơi.

Yêu cầu: Tính tổng lớn nhất của dãy ~A~ sau hai lượt chơi.

Dữ liệu vào

• Dòng đầu chứa số nguyên ~N~ là độ dài của dãy số ~(2 \leq N \leq 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \dots, a_N~ ~(-10^9 \leq a_i \leq 10^9)~ là các phần tử ban đầu của dãy.

Dữ liệu ra

Một số nguyên dương duy nhất thỏa yêu cầu đề bài.

Ví dụ

Input

4
-1 2 -3 -4

Output

10

Giải thích

• Lượt 1 thực hiện đổi dấu từ vị trí $3$ đến vị trí $4$, ta được dãy số: ~-1~ ~2~ ~3~ ~4~
• Lượt 2 thực hiện đổi dấu vị trí $1$, ta được dãy số: ~1~ ~2~ ~3~ ~4~.

Tổng lớn nhất ta đat được là: ~1 + 2 + 3 + 4 = 10~.