{"code":"linegame09","name":"LINEGAME","description":"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.$\r\n\r\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}$.\r\n\r\n**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.\r\n\r\n

Input

\r\n\r\n- 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ố;\r\n- 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.\r\n \r\n

Output

\r\n\r\n- 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\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 7\r\n 4 9 2 4 1 3 7\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 17\r\n ```\r\n \r\n ??? warning \"Note\" \r\n ![Giải thích](https://i.imgur.com/foobbrZ.png)","points":1000.0,"partial":false,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}