You are given an array $a$ consisting of $n$ integers. You want to distribute these $n$ integers into two groups $s_1$ and $s_2$ (groups can be empty) so that the following conditions are satisfied:

For each $i$ $(1 \leq i \leq n)$, $a_i$ goes into exactly one group.

The value $|sum(s_1)| - |sum(s_2)|$ is the maximum possible among all such ways to distribute the integers.

Here $sum(s_1)$ denotes the sum of the numbers in the group $s_1$, and $sum(s_2)$ denotes the sum of the numbers in the group $s_2$.

Determine the maximum possible value of $|sum(s_1)| - |sum(s_2)|$.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ $(1 \leq t \leq 2 \cdot 10^4)$  — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ $(1 \leq n \leq 10^5)$  — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1,a_2 \ldots a_n$ $(-10^9 \leq a_i \leq 10^9)$  — elements of the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.


-----Output-----

For each test case, output a single integer  — the maximum possible value of $|sum(s_1)| - |sum(s_2)|$.


-----Examples-----

Input
4
2
10 -10
4
-2 -1 11 0
3
2 3 2
5
-9 2 0 0 -4
Output
0
8
7
11


-----Note-----

In the first testcase, we can distribute as $s_1 = \{10\}$, $s_2 = \{-10\}$. Then the value will be $|10| - |-10| = 0$.

In the second testcase, we can distribute as $s_1 = \{0, 11, -1\}$, $s_2 = \{-2\}$. Then the value will be $|0 + 11 - 1| - |-2| = 10 - 2 = 8$.

In the third testcase, we can distribute as $s_1 = \{2, 3, 2\}$, $s_2 = \{\}$. Then the value will be $|2 + 3 + 2| - |0| = 7$.

In the fourth testcase, we can distribute as $s_1 = \{-9, -4, 0\}$, $s_2 = \{2, 0\}$. Then the value will be $|-9 - 4 + 0| - |2 + 0| = 13 - 2 = 11$.

Source: codeforces | Difficulty: EASY
Tags: Greedy algorithms

Constructive algorithms


Solutions:
for s in [*open(0)][2::2]:
	print(abs(sum(map(int, s.split()))))


for a in [*open(0)][2::2]:
	print(abs(sum(map(int, a.split()))))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(abs(sum(a)))


import sys
sys.setrecursionlimit(10 ** 9)
input = lambda : sys.stdin.readline().strip('\r\n')
from collections import defaultdict as dd, deque
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(abs(sum(arr)))


for g in [*open(0)][2::2]:
	print(abs(sum(map(int, g.split()))))


for l in [*open(0)][2::2]:
	print(abs(sum(map(int, l.split()))))


t = int(input())
result = ''
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	r = abs(sum(a))
	result += str(r)
	result += '\n'
print(result[:-1])


data_count = int(input())
data_arrs = []
for i in range(data_count):
	arr_length = int(input())
	data_arrs.append(list(map(int, input().strip().split()))[:arr_length])
for data_arr in data_arrs:
	print(abs(sum(data_arr)))
4


import sys
import math
import bisect
import heapq
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from functools import cmp_to_key
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, stdin.readline().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, stdin.readline().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
sort = lambda x, compare: sorted(x, key=cmp_to_key(compare))
mod = 1000000007

def sumMod(a, b):
	return (a % mod + b % mod) % mod
for i in range(stdint()):
	n = stdint()
	print(abs(sum(seq())))


n = int(input())
sums = []
for i in range(n):
	input()
	sums.append(abs(sum(map(int, input().split()))))
for i in sums:
	print(i)


import sys
input = sys.stdin.readline

def solution(items: list, n: int):
	(s1, s2) = (0, 0)
	for item in items:
		if item < 0:
			s2 += item
		else:
			s1 += item
	(s1, s2) = (abs(s1), abs(s2))
	return abs(s1 - s2)
t = int(input())
for _ in range(t):
	n = int(input())
	items = list(map(int, input().split()))
	print(solution(items, n))


import sys
input = sys.stdin.readline

def readList():
	return list(map(int, input().split()))

def readInt():
	return int(input())

def readInts():
	return map(int, input().split())

def readStr():
	return input().strip()

def solve():
	n = readInt()
	arr = readList()
	return abs(sum(arr))
for _ in range(int(input())):
	print(solve())


t = int(input())
d = []
for i in range(t):
	n = int(input())
	f = [int(i) for i in input().split()]
	d.append(abs(sum(f)))
for i in d:
	print(i, end='\n')


from collections import defaultdict
from sys import stdin, stdout
import string

def solution(N, A):
	sum_plus = 0
	sum_minus = 0
	for a in A:
		if a >= 0:
			sum_plus += a
		elif a < 0:
			sum_minus += abs(a)
	if sum_plus > sum_minus:
		return sum_plus - sum_minus
	else:
		return sum_minus - sum_plus
test_cases = int(stdin.readline())
for it in range(test_cases):
	N = int(stdin.readline())
	A = list(map(int, stdin.readline().split()))
	print(solution(N, A))


t = int(input())
answers = []
for i in range(t):
	n = int(input())
	l = [int(number) for number in input().split()]
	answers.append(abs(sum(l)))
for j in range(t):
	print(answers[j])


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
test_cases = inp()
inp_arr = []
for i in range(test_cases):
	n = inp()
	nums = inlt()
	inp_arr.append(nums)

def findResult(nums):
	p_nums = []
	n_nums = []
	for num in nums:
		if num > 0:
			p_nums.append(num)
		elif num < 0:
			n_nums.append(num)
	s1 = abs(abs(sum(p_nums)) - abs(sum(n_nums)))
	return s1
result = [findResult(nums) for nums in inp_arr]
for m in result:
	print(m)


t = int(input())
l = []
for i in range(t):
	ma = mi = 0
	input()
	l1 = list(map(int, input().split()))
	for i in l1:
		if i > 0:
			ma += i
		else:
			mi += i
	l.append(abs(ma + mi))
for i in l:
	print(i)


import sys
inputs = ''.join(sys.stdin.readlines()).strip().split('\n')[2::2]
for x in inputs:
	summation = 0
	for i in x.split():
		summation += int(i)
	print(abs(summation))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	(sum1, sum2) = (0, 0)
	for i in lst:
		if i > 0:
			sum1 += i
		else:
			sum2 += i
	print(abs(abs(sum1) - abs(sum2)))


from collections import Counter, defaultdict
import sys
import math

def sol(arr, n):
	return abs(sum(arr))
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	return str(input())

def invr():
	return map(int, input().split())
T = inp()
for i in range(T):
	n = inp()
	arr = inlt()
	print(sol(arr, n))


first_test = int(input())
list_of_sums = []
for i in range(0, first_test):
	second_test = int(input())
	taking_input_list = list(map(int, input().split(' ')))
	output_sum = sum(taking_input_list)
	if output_sum < 0:
		list_of_sums.append(output_sum * -1)
	else:
		list_of_sums.append(output_sum)
print(*list_of_sums, sep='\n')


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def ins():
	s = input()
	return list(s[:len(s) - 1])

def inl():
	return map(int, input().split())
T = inp()
for tt in range(0, T):
	n = inp()
	x = list(inl())
	sp = sum(filter(lambda x: x > 0, x))
	sn = sum(map(abs, filter(lambda x: x <= 0, x)))
	if sn > sp:
		(sp, sn) = (sn, sp)
	print(sp - sn)


n = int(input())
ans = []
for i in range(n):
	t = int(input())
	arr = input().split()
	arr = [int(x) for x in arr]
	sum_n = sum_p = 0
	for k in arr:
		if k < 0:
			sum_n += k
		else:
			sum_p += k
	ans.append(abs(abs(sum_p) - abs(sum_n)))
for i in ans:
	print(i)


input = __import__('sys').stdin.readline
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(num1, num2) = (0, 0)
	for i in arr:
		if i > 0:
			num1 += i
		else:
			num2 += i
	if abs(num1) > abs(num2):
		print(abs(num1) - abs(num2))
	else:
		print(abs(num2) - abs(num1))


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_string():
	return list(map(str, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

def get_print_int(x):
	sys.stdout.write(str(x) + '\n')

def get_print(x):
	sys.stdout.write(x + '\n')

def get_print_int_same(x):
	sys.stdout.write(str(x) + ' ')

def get_print_same(x):
	sys.stdout.write(x + ' ')
from sys import maxsize

def solve():
	for _ in range(get_int()):
		n = get_int()
		arr = get_list()
		(pos, neg) = (0, 0)
		for i in range(n):
			if arr[i] >= 0:
				pos += arr[i]
			else:
				neg += -1 * arr[i]
		get_print_int(abs(pos - neg))
solve()


t = int(input())
answers = []
for _ in range(t):
	s1 = []
	s2 = []
	n = int(input())
	a = list(map(int, input().split()))
	for i in a:
		if i >= 0:
			s1.append(i)
		else:
			s2.append(i)
	answers.append(abs(abs(sum(s1)) - abs(sum(s2))))
for i in answers:
	print(i)


num_input = int(input())
tests = []
for i in range(num_input):
	n = input()
	nums = tuple([int(j) for j in input().split()])
	tests.append(nums)

def count_max(arr):
	spos = 0
	sneg = 0
	for num in arr:
		if num > 0:
			spos += num
		else:
			sneg += num
	return abs(spos + sneg)
for test in tests:
	print(count_max(test))


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	a1 = 0
	b1 = 0
	for i in a:
		if i < 0:
			b1 += i
		else:
			a1 += i
	print(max(abs(a1) - abs(b1), abs(b1) - abs(a1)))


amount = int(input())
testcasenum = []
array = []
for i in range(amount):
	testcasenum.append(int(input()))
	array.append(list(map(int, input().split(' '))))
for i in range(amount):
	s = abs(sum(array[i]))
	print(s)


def numbers():
	n = int(input())
	firstarray = []
	secondarray = []
	result = []
	for i in range(n):
		len_array = int(input())
		array = map(int, input().split())
		for j in array:
			if j <= 0:
				secondarray.append(j)
			else:
				firstarray.append(j)
		result.append(abs(abs(sum(firstarray)) - abs(sum(secondarray))))
		secondarray = []
		firstarray = []
	return print(*result, sep='\n')
numbers()


t = int(input())
sums = []
while t > 0:
	t -= 1
	n = int(input())
	a = [int(x) for x in input().split()]
	sum = 0
	for i in range(n):
		sum += a[i]
	sums.append(abs(sum))
for i in range(len(sums)):
	print(sums[i])


n = int(input())
res = []
for m in range(n):
	m = int(input())
	ks = [int(x) for x in input().split()]
	sp = abs(sum([k for k in ks if k > 0]))
	sn = abs(sum([k for k in ks if k < 0]))
	res.append(abs(sp - sn))
for x in res:
	print(x)


from sys import stdin
T = int(stdin.readline().rstrip())
for _ in range(T):
	N = int(stdin.readline().rstrip())
	l = list(map(int, stdin.readline().rstrip().split()))
	l.sort()
	s1 = 0
	s2 = 0
	for i in l:
		if i < 0:
			s1 -= i
		else:
			s2 += i
	if s1 > s2:
		print(s1 - s2)
	else:
		print(s2 - s1)


import sys

def maxDiffSubsets(arr):
	totalSum = 0
	pos = False
	neg = False
	min = sys.maxsize
	for i in range(len(arr)):
		totalSum += arr[i]
		if arr[i] > 0:
			pos = True
		if arr[i] < 0:
			neg = True
		if arr[i] < min:
			min = arr[i]
	if pos and neg:
		return abs(totalSum)
	elif pos or neg:
		return abs(totalSum)
	else:
		return abs(totalSum) - 2 * abs(min)
t = int(input())
res = []
for i in range(0, t):
	n = int(input())
	mass = list(map(int, input().split()))
	res.append(maxDiffSubsets(mass))
for i in res:
	print(i)


n = int(input())
ans = []
for i in range(n):
	input()
	lis = list(map(int, input().split(' ')))
	pos = [i for i in lis if i >= 0]
	neg = [i for i in lis if i < 0]
	if neg == []:
		ans.append(sum(pos))
	elif sum(pos) > -1 * sum(neg):
		ans.append(sum(pos) + sum(neg))
	else:
		ans.append(abs(sum(neg) + sum(pos)))
for i in ans:
	print(i)


t = int(input())
a = []
n = []
for i in str('a' * t):
	n.append(int(input()))
	a.append(list(map(int, input().split())))
k = 0
i = 0
l = 0
v = 0
b = 0
for k in str('a' * t):
	h = 0
	for i in 'a' * n[l]:
		v = v + a[b][h]
		h += 1
	print(abs(v))
	v = 0
	b += 1
	l += 1


t = int(input())
while t > 0:
	a_len = int(input())
	a = list(map(int, input().split()))
	print(abs(sum(a)))
	t -= 1


I = input
for _ in ' ' * int(input()):
	I()
	print(abs(sum(map(int, I().split()))))


import fileinput

def main():
	lines = fileinput.input()
	ntests = int(next(lines).rstrip('\n'))
	for test in range(ntests):
		n = int(next(lines).rstrip('\n'))
		numbers = [int(num) for num in next(lines).rstrip('\n').split(' ')]
		pos = [num for num in numbers if num > 0]
		neg = [num for num in numbers if num <= 0]
		print(max(sum(pos) + sum(neg), -(sum(pos) + sum(neg))))
main()


n = input()
p = []
for i in range(0, 2 * int(n)):
	l = input()
	p.append(l)
for j in range(1, 2 * int(n), 2):
	h = [int(i) for i in p[j].split()]
	po = 0
	ne = 0
	for k in h:
		if k >= 0:
			po = po + k
		else:
			ne = ne + k
	if po >= ne * -1:
		print(f'{po + ne}')
	else:
		print(f'{-1 * ne - po}')


t = int(input())
for _ in range(t):
	n = int(input())
	(*a,) = map(int, input().split())
	print(abs(sum(a)))


t = int(input())
l = []
for i in range(t):
	n = int(input())
	a = list(input().split())
	for i in range(len(a)):
		a[i] = int(a[i])
	x = []
	y = []
	for i in a:
		if i < 0:
			y.append(i)
		else:
			x.append(i)
	l.append(abs(sum(x) - abs(sum(y))))
for i in l:
	print(i)


def max_sum(l, arr):
	max_pos = 0
	max_neg = 0
	s = sum(arr)
	for i in range(l):
		if arr[i] >= 0:
			max_pos += arr[i]
		else:
			max_neg += arr[i]
	if max_pos >= abs(max_neg):
		sum1 = max_pos
		sum2 = s - max_pos
		return abs(sum1) - abs(sum2)
	else:
		sum1 = max_neg
		sum2 = s - max_neg
		return abs(sum1) - abs(sum2)
T = int(input())
ans = []
for i in range(T):
	l = int(input())
	arr = [int(i) for i in input().split(' ')]
	k = max_sum(l, arr)
	ans.append(k)
for i in ans:
	print(i)


import sys
from bisect import bisect_left, bisect_right
from heapq import heapify, heappush, heappop
from collections import deque
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
from collections import deque, defaultdict
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]
for _ in range(ii()):
	n = il()
	arr = il()
	n = 0
	p = 0
	for k in arr:
		if k < 0:
			n += abs(k)
		else:
			p += k
	print(abs(p - n))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(abs(sum(l)))


def getint():
	return [int(i) for i in input().split()]

def get():
	return int(input())

def S():
	for test in range(int(input())):
		solve()

def solve():
	n = get()
	a = getint()
	print(abs(sum(a)))
S()


from sys import stdin

def readint():
	return int(stdin.readline())

def readarray(typ):
	return list(map(typ, stdin.readline().split()))

def readmatrix(n):
	M = []
	for _ in range(n):
		row = readarray(int)
		assert len(row) == n
		M.append(row)
	return M

def mult(M, v):
	n = len(M)
	return [sum((M[i][j] * v[j] for j in range(n))) for i in range(n)]
t = readint()
for _ in range(t):
	n = readint()
	arr = readarray(int)
	arr_s = sorted(arr)
	g1 = []
	g2 = []
	for i in arr_s:
		if i < 0:
			g2.append(i)
		else:
			g1.append(i)
	print(abs(sum(g1) - abs(sum(g2))))


def sol(lst):
	return abs(sum(lst))
T = int(input())
for test_case in range(1, T + 1):
	n = int(input())
	lst = [int(s) for s in input().split(' ')]
	s = sol(lst)
	print(s)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	res = sum(arr)
	print(abs(res))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))
	print(abs(sum(a)))


def function():
	lengthofarray = int(input())
	sumpositive = 0
	sumnegative = 0
	array = input()
	list_array = array.split(' ')
	for item in list_array:
		x = int(item)
		if x >= 0:
			sumpositive += x
		else:
			sumnegative -= x
	difference = sumpositive - sumnegative
	if difference < 0:
		difference *= -1
	print(difference)
testcases = int(input())
for x in range(testcases):
	function()


test = int(input())
while test:
	n = int(input())
	a = [int(x) for x in input().split()]
	print(abs(sum(a)))
	test -= 1


t = int(input())
tt = []
for i in range(t):
	n = int(input())
	temp = []
	h = input().split(' ')
	hh = list(map(int, h))
	tt.append(hh)
for i in range(t):
	k = tt[i]
	sk = sum(k)
	kp = list(map(abs, k))
	skp = sum(kp)
	skpi = int((skp + sk) / 2)
	skoi = sk - skpi
	if abs(skpi) > abs(skoi):
		print(abs(skpi) - abs(skoi))
	else:
		print(abs(skoi) - abs(skpi))


def main():
	n = int(input())
	totales = []
	for i in range(n):
		s1 = []
		s2 = []
		test = int(input())
		lista = input().split()
		lista = [int(x) for x in lista]
		for j in range(test):
			if lista[j] < 0:
				s2.append(lista[j])
			else:
				s1.append(lista[j])
		s1r = abs(sum(s1))
		s2r = abs(sum(s2))
		total = abs(s1r - s2r)
		totales.append(total)
	for i in range(len(totales)):
		print(totales[i])
main()


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(abs(sum(arr)))


import sys
t = int(sys.stdin.readline())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	s = sum(lst)
	print(abs(s))


for i in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	print(abs(sum(list1)))


def main():
	for _ in range(int(input())):
		arr_len = int(input())
		arr = list(map(int, input().split()))
		print(abs(sum(arr)))
main()


for _ in range(int(input())):
	n_ = input()
	n = input().split()
	total = 0
	for i in range(int(n_)):
		total += int(n[i])
	print(abs(total))


t = int(input())
for i in range(t):
	n = int(input())
	s = 0
	for c in input().split():
		s += int(c)
	print(abs(s))


num = int(input())
for i in range(0, num):
	n = int(input())
	li = input().split()
	li = [int(x) for x in li]
	s = sum(li)
	print(abs(s))


for _ in range(int(input())):
	_ = int(input())
	print(abs(sum(map(int, input().split()))))


for _ in range(int(input())):
	n = int(input())
	a = [int(no) for no in input().split(' ')]
	print(abs(sum(a)))


t = int(input())
for g in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	summ = sum(a)
	if summ < 0:
		print(-summ)
	else:
		print(summ)


for i in range(int(input())):
	a = input()
	l = map(int, input().split())
	print(abs(sum(l)))


t = int(input())
for test in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	res = abs(sum(a))
	print(res)


tesrty = int(input())
for tc4tr in range(tesrty):
	hgawq = int(input())
	lsrbh = list(map(int, input().split()))
	sumdevf = sum(lsrbh)
	print(abs(sumdevf))


for _ in range(int(input())):
	ven = int(input())
	print(abs(sum(list(map(int, input().split())))))