THỰC HÀNH

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 + ... + (-1)^k-1a_ik

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 chứa số nguyên dương N.
• Dòng thứ 2 chứa N số nguyên a₁, a₂, …, a_N, mỗi số cách nhau một dấu cách.

Dữ liệu ra:

Một số nguyên duy nhất là giá trị lớn nhất có thể thực hiện được ở một lượt chơi.

Ví dụ:

Dữ liệu vào:
7
4 9 2 4 1 3 7

Dữ liệu ra:
17

Giải thích: Ta lần lượt chọn 5 số như hình sau:

Giới hạn: 1 ≤ N ≤ 10⁶, 1 ≤ a_i ≤ 10⁴