{"code":"maxdiff","name":"Trọng số khoản (Hard ver.)","description":"Định nghĩa trọng số của một nhóm số nguyên là độ chênh lệch giữa phần tử lớn nhất và phần tử nhỏ nhất trong nhóm đó. (Nhóm có thể có 1 phần tử)\r\n\r\nVí dụ trọng số của nhóm $(3,1,7,2)$ là $6$, trọng số của nhóm $(40,40)$ là $0$, trọng số của nhóm $(1208)$ là $0$.\r\n\r\nCho 1 dãy gồm $n$ phần tử, phần tử thứ $i$ có giá trị là $a_i$.\r\n\r\n**Yêu cầu:**\r\n- Mỗi nhóm là 1 dãy các số liên tiếp.\r\n- Giá trị của dãy số bằng tổng trọng số của tất cả các nhóm. Hãy tìm cách chia sao cho tổng trọng số đạt giá trị lớn nhất.\r\n\r\n#### Input\r\n\r\n- Dòng 1: chứa số nguyên $n (1 \\le n \\le 10^5)$\r\n- Dòng 2: chứa $n$ số nguyên $a_1, a_2, ..., a_n (-10^9 \\le a_i \\le 10^9)$\r\n\r\n#### Output\r\n\r\n- Ghi ra giá trị lớn nhất của dãy.\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n        ```sample\r\n        6\r\n        1 9 6 7 1 6\r\n        ```\r\n    \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        14\r\n        ```\r\n    \r\n    ??? warning \"Note\"  \r\n\r\n        Dãy số [1 9 6 7 1 6] có thể chia được thành các nhóm: [1 9] | [6 7 1] | [6].","points":500.0,"partial":true,"time_limit":1.0,"memory_limit":1048576,"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}}