Giải bài trực tuyến

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

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:

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

Kết quả:

• 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ụ:

Dữ liệu
 
Kết quả


7
4 9 2 4 1 3 7
17