Trò chơi với băng số

Trò chơi với băng số là trò chơi tham gia trúng thưởng được mô tả như sau: Có một băng hình chữ nhật được chia ra làm $n$ ô vuông, đánh số từ trái qua phải bắt đầu từ $1$. Trên ô vuông thứ $i$ người ta ghi một số nguyên dương $a_i$, $i=1,2,\dots ,n$. Ở một lượt chơi, người tham gia trò chơi được quyền lựa chọn một số lượng tùy ý các ô trên băng số. Giả sử theo thứ tự từ trái qua phải, người chơi lựa chọn các ô $i_1,i_2,\dots ,i_k$. Khi đó điểm số mà người chơi đạt được sẽ là:

$$a_{i_1}-a_{i_2}+\dots +(-1{)}^{k-1}{a}_{i_k}$$

Yêu cầu: Hãy tính số điểm lớn nhất có thể đạt được từ một lượt chơi.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương $n$ ($n\le {10}^6$) là số lượng ô của băng số;
• Dòng thứ hai chứa $n$ số nguyên dương $a_1,a_2,\dots ,a_n$ ($a_i\le {10}^4$, $i=1,2,\dots ,n$) ghi trên băng số. Các số liên tiếp trên cùng dòng được ghi cách nhau bởi ít nhất một dấu cách.

Dữ liệu ra

Một số nguyên duy nhất là số điểm lớn nhất có thể đạt được từ một lượt chơi.

Ràng buộc

• $1\le n\le {10}^6$.
• $1\le a_i\le {10}^4$.

Subtasks

• Subtask 1 ($60\%$ số test): $1\le n\le 20$.
• Subtask 2 ($40\%$ số test): $20<n\le {10}^6$.

Mỗi subtask gồm nhiều test, mỗi test được chấm điểm riêng.

Ví dụ