Có \(N\) số nguyên, \(A_1, A_2, ..., A_N\), được sắp xếp theo thứ tự này.

Bạn có thể thực hiện phép toán sau trên dãy số nguyên này bất kỳ số lần nào:

• Phép toán: Chọn một số nguyên \(i\) thỏa mãn \(1 \leq i \leq N-1\). Nhân cả \(A_i\) và \(A_{i+1}\) với \(-1\).

Gọi \(B_1, B_2, ..., B_N\) là dãy số nguyên sau khi bạn thực hiện các phép toán.

Tìm giá trị lớn nhất có thể của \(B_1 + B_2 + ... + B_N\).

Ràng buộc

• Tất cả các giá trị đầu vào là số nguyên.
• \(2 \leq N \leq 10^5\)
• \(-10^9 \leq A_i \leq 10^9\)

INPUT FORMAT

Đầu vào được cung cấp từ Standard Input theo định dạng sau:

N
A_1
A_2
...
A_N

OUTPUT FORMAT

In ra giá trị lớn nhất có thể của \(B_1 + B_2 + ... + B_N\).

Ví dụ:

Input

3
-10 5 -4

Output

19

Nếu chúng ta thực hiện phép toán như sau:

Chọn \(1\) làm \(i\), điều này thay đổi dãy số thành \(10, -5, -4\). Chọn \(2\) làm \(i\), điều này thay đổi dãy số thành \(10, 5, 4\). chúng ta có \(B_1 = 10, B_2 = 5, B_3 = 4\). Tổng ở đây, \(B_1 + B_2 + B_3 = 10 + 5 + 4 = 19\), là kết quả lớn nhất có thể.

Input

5
10 -4 -8 -11 3

Output

30

Giải thích ví dụ mẫu

Ví dụ 1:

• Input:

  3 -10 5 -4

• Giải thích:

  • Thay đổi dãy số thành 10, -5, -4 và sau đó thành 10, 5, 4, tổng đạt 19.

Ví dụ 2:

• Input:

  5 10 -4 -8 -11 3

• Giải thích:

  • Thực hiện phép toán để có dãy số 10, 4, 8, 11, 3, tổng là 30.
    

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House