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 ô \(i_1, i_2, ..., i_k\). Khi đó điểm số mà người chơi đạt được sẽ là: \(a_{i_1} - a_{i_2} + ... + (-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.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) \((n \leq 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 \leq 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.

Output

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

Example

7
4 9 2 4 1 3 7

17