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.

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}, \dots, a_{n}~ ~(a_{i} \leq 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.

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.

Giới hạn

60% số tests ứng với 60% số điểm của bài có ~1 \leq n \leq 20~.

Sample Input

7
4 9 2 4 1 3 7

Sample Output

17

Note