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, ..., 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 ô ~i1, i2, ..., ik~. Khi đó điểm số mà người chơi đạt được sẽ là: ~a_{i1} - a_{i2} + ... + (-1)^{k-1}a_{ik}~

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 ≤ 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, ..., a_n~ (~a_i ≤ 10^4~, ~i = 1, 2, ..., 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:

• Ghi 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.

Ví dụ:

Input

7
4 9 2 4 1 3 7

Output

17

Ràng buộc:

• 30% số điểm của bài có ~1 < n ≤ 20~
• 40% số test thỏa ~1 ≤ n ≤ 5000~
• 30% số test thỏa ~1000 < n ≤ 1~