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₁, i₂, …, i_k.
Khi đó điểm số mà người chơi đạt được sẽ là: a_i1 - a_i2 + a_i3 - a_i4 + … + (-1)^k-1a_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.

Input

Dòng đầu tiên chứa số nguyên dương n (n ≤ 10⁶) là số lượng ô của bảng số.
Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, a_n (a_i ≤ 10⁴, 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.

Ràng buộc

60% số test ứng với 60% số điểm của bài có 1 ≤ n ≤ 20.

Ví dụ

Input
7
4 9 2 4 1 3 7

Output
17

Giải thích: Người chơi chọn các ô 2, 3, 4, 5, 6, 7. Khi đó điểm số = 9 - 2 + 4 - 1 + 3 - 7 = 17.