CF2178C First or Second

There are $ n $ children standing in a line, where the niceness of the $ i $ -th child is $ a_i $ . Santa is deciding which children belong on the nice list and which belong on the naughty list. An integer $ X $ is initially set to $ 0 $ . Santa will perform the following operation exactly $ n-1 $ times: - Choose the first or second child in line and remove them from the line. - Let $ w $ be the niceness of the chosen child. - If the first child was chosen, add them to the nice list and add $ w $ to $ X $ . - If the second child was chosen, add them to the naughty list and subtract $ w $ from $ X $ . Note that after all operations, exactly one child remains unassigned to a list. Determine the maximum possible value of $ X $ that Santa can obtain after all $ n-1 $ operations.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 2\le n\le 2\cdot 10^5 $ ) — the number of children. The second line contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ -10^9\le a_i\le 10^9 $ ) — the niceness of each child. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot 10 ^ 5 $ .

For each test case, print a single integer — the maximum possible value of $ X $ that Santa can obtain after all $ n-1 $ operations.

In the first test case, Santa will perform exactly one operation. If he chooses the first child, he will add $ a_1=2 $ to $ X $ to get $ X=2 $ ; if he chooses the second child, he will subtract $ a_2=-3 $ from $ X $ to get $ X=3 $ . Thus, the answer is $ 3 $ . In the second test case, it is optimal to select the first child in all three operations. The value of $ X $ will be $ 1+4+3=8 $ . In the third test case, below is an optimal sequence of operations: \#TypeNiceness of remaining children $ X $ after operation0— $ [-4, 2, 3, -6] $ $ 0 $ 1First $ [2, 3, -6] $ $ -4 $ 2First $ [3, -6] $ $ -2 $ 3Second $ [3] $ $ 4 $ In the fourth test case, below is an optimal sequence of operations: \#TypeNiceness of remaining children $ X $ after operation0— $ [-2, -3, 4, 10, -9] $ $ 0 $ 1Second $ [-2, 4, 10, -9] $ $ 3 $ 2First $ [4, 10, -9] $ $ 1 $ 3First $ [10, -9] $ $ 5 $ 4First $ [-9] $ $ 15 $