Tổng kỳ diệu

Cho một dãy gồm $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Bạn được phép thực hiện lần lượt đúng hai thao tác sau:

1. Chọn một tiền tố của dãy (phần đầu dãy, có thể rỗng) và nhân tất cả các phần tử trong đó với $-1$.
2. Sau đó chọn một hậu tố của dãy (phần cuối dãy, có thể rỗng) và nhân tất cả các phần tử trong đó với $-1$.

Tiền tố và hậu tố được chọn có thể giao nhau. Khi đó mỗi phần tử thuộc phần giao bị nhân với $-1$ hai lần, tức là giữ nguyên giá trị ban đầu.

Hãy tìm tổng lớn nhất của dãy có thể thu được sau hai thao tác trên.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$, số phần tử của dãy.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

Một số nguyên duy nhất là tổng lớn nhất có thể thu được.

Ràng buộc

• $1\le n\le {10}^5$
• $-{10}^4\le a_i\le {10}^4$

Ví dụ