翻译

题目描述: 学习，学习，再学习--瓦勒拉每天都要这样做。他在数学学校学习，数学是那里的主要学科。数学老师非常喜欢她的学科，并试图在孩子们身上培养这种爱。这就是为什么她总是给她的学生做大而困难的作业。尽管瓦莱拉是最好的学生之一，他还是没能完成新的家庭作业。所以他才找你帮忙。他有以下任务。给出了一个N个数字的序列。序列的前缀是序列的一部分（可能是空的），从序列的开始取。序列的后缀是序列的一部分（可能是空的），取自序列的结尾。允许用顺序顺序进行两个操作。第一个操作是取序列的某个前缀，并将该前缀中的所有数乘以-1。第二个操作是取一些后缀，并将其中的所有数字乘以-1。选择的前缀和后缀可能相交。应用描述的操作可以得到的序列的最大总和是多少？

输入输出格式

输入格式： 输入的第一行给出了测试用例的数目，t.t测试用例如下，每行有两行。第一行包含整数N(1≤N≤10^{5} 5 ）——序列中元素的数量。第二行包含N个整数ai(-10^{4} 4 ≤ai≤10^{4} 4 ）——序列本身。 输出格式： 对于每个测试用例，输出一行，其中包含问题的答案 输入输出样例

输入样例#1： 3 3 -1 -2 -3 5 -4 2 0 5 0 5 -1 10 -5 10 -2 输出样例#1： 6 11 18