CF33C - Wonderful Randomized Sum

题目描述 学习！学习！再学习！ $Valera$不得不每天都学习，他正在一个数学被作为主科的学校学习，这位数学老师可是非常喜欢她的学科。而且！她要把这种爱栽种给她的学生：于是学生就有了成堆的$homework$，然后，你就需要出动了。。$Valera$虽然是班里最好的学生，但他还是做不完这些作业，你得帮他。 $Valera$有一下任务： 首先给出一个长度为$n$的数列， 定义一个数列的前缀代表这个数列的前$i (0<=i<=n)$个数，一个数列的后缀代表这个数列的后$j(0<=j<=n)$个数。 现在你要执行两次操作： 对于第一次操作，你选择一个前缀，把这些数全部变为相反数。（乘$-1$） 对于第二次操作，你选择一个后缀，把这些数字全部变为相反数。（乘$-1$） 这两个操作可以有交叉，也就是说，可能存在一些数被乘两次$-1$. 现在，$Valera$想要知道，经过这两次操作，这个数列所有数字的总和最大是多少。 有多组测试数据。。

Learn, learn and learn again — Valera has to do this every day. He is studying at mathematical school, where math is the main discipline. The mathematics teacher loves her discipline very much and tries to cultivate this love in children. That's why she always gives her students large and difficult homework. Despite that Valera is one of the best students, he failed to manage with the new homework. That's why he asks for your help. He has the following task. A sequence of n numbers is given. A prefix of a sequence is the part of the sequence (possibly empty), taken from the start of the sequence. A suffix of a sequence is the part of the sequence (possibly empty), taken from the end of the sequence. It is allowed to sequentially make two operations with the sequence. The first operation is to take some prefix of the sequence and multiply all numbers in this prefix by - 1. The second operation is to take some suffix and multiply all numbers in it by - 1. The chosen prefix and suffix may intersect. What is the maximum total sum of the sequence that can be obtained by applying the described operations?

The first line of the input gives the number of test cases, T. T test cases follow, each with two lines. The first line contains integer n (1 ≤ n ≤ 10 $ ^{5} $ ) — amount of elements in the sequence. The second line contains n integers ai ( - 10 $ ^{4} $ ≤ ai ≤ 10 $ ^{4} $ ) — the sequence itself.

For each test case, output one line containing the answer to the problem.

3
3
-1 -2 -3
5
-4 2 0 5 0
5
-1 10 -5 10 -2

6
11
18