{"code":"twogroups","name":"Two Groups","description":"Cho dãy số $a$ gồm $n$ phần tử. Hãy tìm cách chia dãy số này thành 2 dãy con liên tiếp $s_1,s_2$ (có thể là dãy rỗng) sao cho:\r\n - Với mọi $1 \\le i \\le n$, $a_i$ thuộc đúng một nhóm.\r\n - Tổng $|sum(s_1)|-|sum(s_2)|$ đạt giá trị lớn nhất có thể. Trong đó $sum(s_1)$ thể hiện cho tổng tất cả các phần tử của dãy $s_1$\r\n\r\n

Input

\r\n - Dòng thứ nhất chứa số nguyên dương $t$ $(t \\le 10^3)$ - số testcase;\r\n - Mỗi testcase tiếp theo có dạng như sau:\r\n - Dòng thứ nhất chứa số nguyên dương $n$ $(n \\le 10^3)$;\r\n - Dòng thứ hai 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 - Ứng với mỗi test case in ra giá trị $|sum(s_1)|-|sum(s_2)|$ lớn nhất có thể.\r\n\r\n

Example

\r\n!!! question \"Test 1\"\r\n ???+ \"Sample input\"\r\n ```sample\r\n 4\r\n 2\r\n 10 -10\r\n 4\r\n -2 -1 11 0\r\n 3\r\n 2 3 2\r\n 5\r\n -9 2 0 0 -4\r\n ```\r\n ???+ success \"Sample output\"\r\n ```sample\r\n 0\r\n 8\r\n 7\r\n 11\r\n ```\r\n ???+ warning \"Explanation\"\r\n - Trong testcase thứ nhất, ta có thể chia thành hai dãy $s_1=\\{10\\}$, $s_2=\\{-10\\}$.\r\n - Trong testcase thứ hai, ta có thể chia thành hai dãy $s_1=\\{0;11;-1\\}$, $s_2=\\{-2\\}$\r\n - Trong testcase thứ ba, ta có thể chia thành hai dãy $s_1=\\{2;3;2\\}$, $s_2=\\{\\}$\r\n - Trong testcase thứ tư, ta có thể chia thành hai dãy $s_1=\\{-9;-4;0\\}$, $s_2=\\{2;0\\}$\r\n\r\n

Note

\r\n- Nguồn: *CF Round 832 div 2*","points":800.0,"partial":false,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[4,34,36,37,5,6,11,12,14,28,38,39,29,27,35,26,10,32,1,8,33,41,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}