Chef has an array A of length N. He defines the *alternating sum* of the array as:
S = |A_{1}| - |A_{2}| + |A_{3}| - |A_{4}| + \ldots (-1)^{N-1}\cdot |A_{N}|

Chef is allowed to perform the following operation on the array at most once:
Choose two indices i and j (1 ≤ i <  j ≤ N) and swap the elements A_{i} and A_{j}.

Find the maximum *alternating sum* Chef can achieve by performing the operation at most once.

Note: |X| denotes the absolute value of X. For example, |-4| = 4 and |7| = 7.

------ Input Format ------ 

- The first line will contain T - the number of test cases. Then the test cases follow.
- First line of each test case contains a single integer N - size of the array A.
- Second line of each test case contains N space separated integers - denoting the elements of array A.

------ Output Format ------ 

For each testcase, output in a single line, the maximum *alternating sum* Chef can obtain by performing the operation at most once.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 10^{5}$
$-10^{9} ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
2
2
10 -10
7
-3 -2 -1 0 1 2 3

----- Sample Output 1 ------ 
0
6

----- explanation 1 ------ 
Test Case $1$: One optimal way is to perform no operations. Thus the alternating sum is $|10| - |-10| = 10 - 10 = 0$.

Test Case $2$: One optimal way is to choose $i = 2$ and $j = 5$. After swapping, the array is $[-3, 1, -1, 0, -2, 2, 3]$. The alternating sum in this case is $|-3| - |1| + |-1| - |0| + |-2| - |2| + |3| = 6$.

Source: codechef | Difficulty: MEDIUM


Solutions:
from os import path
import sys
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	odd = []
	even = []
	for i in range(n):
		if i + 1 & 1:
			odd.append(abs(a[i]))
		else:
			even.append(abs(a[i]))
	odd.sort()
	even.sort()
	s = sum(odd) - sum(even)
	if odd[0] < even[-1]:
		s -= 2 * odd[0]
		s += 2 * even[-1]
	print(s)


testcase_no = int(input())
for testcases in range(testcase_no):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = [abs(l[i]) for i in range(0, n, 2)]
	l2 = [abs(l[i]) for i in range(1, n, 2)]
	s1 = sum(l1)
	s2 = sum(l2)
	diff1 = s1 - s2
	min1 = abs(min(l1))
	max2 = abs(max(l2))
	new_s1 = s1 - min1 + max2
	new_s2 = s2 - max2 + min1
	diff2 = new_s1 - new_s2
	if diff1 > diff2:
		print(diff1)
	else:
		print(diff2)


for case in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(e, o) = ([], [])
	for i in range(n):
		if i % 2 == 0:
			e.append(abs(l[i]))
		else:
			o.append(abs(l[i]))
	me = min(e)
	mo = max(o)
	se = sum(e)
	so = sum(o)
	if me < mo:
		se = se - me + mo
		so = so - mo + me
	print(se - so)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = []
	b = []
	for i in range(n):
		if i % 2 == 0:
			if l[i] < 0:
				a.append(-1 * l[i])
			else:
				a.append(l[i])
		elif l[i] < 0:
			b.append(-1 * l[i])
		else:
			b.append(l[i])
	a.sort()
	b.sort()
	li = sum(a)
	bi = sum(b)
	st = li - bi
	(a[0], b[len(b) - 1]) = (b[len(b) - 1], a[0])
	q = sum(a)
	w = sum(b)
	ki = q - w
	if st > ki:
		print(st)
	else:
		print(ki)


t = int(input())
for i in range(t):
	n = int(input())
	arr = input().split(' ')
	(l1, l2) = ([], [])
	for j in range(n):
		if j % 2 == 0:
			l1.append(abs(int(arr[j])))
		else:
			l2.append(abs(int(arr[j])))
	l1.sort()
	l2.sort()
	if l1[0] < l2[-1]:
		(l1[0], l2[-1]) = (l2[-1], l1[0])
	print(sum(l1) - sum(l2))


for _ in range(int(input())):
	n = int(input())
	a = [abs(int(x)) for x in input().split()]
	(max_o, min_e) = (0, a[0])
	(sum_o, sum_e) = (0, 0)
	for i in range(n):
		if i % 2:
			sum_o += a[i]
			if a[i] > max_o:
				max_o = a[i]
		else:
			sum_e += a[i]
			if a[i] < min_e:
				min_e = a[i]
	d = sum_e - sum_o
	if max_o > min_e:
		d += 2 * (max_o - min_e)
	print(d)


def func():
	n = int(input())
	arr = list(map(int, input().split()))
	m = []
	t = []
	for i in range(1, n, 2):
		m.append(abs(arr[i - 1]))
		t.append(abs(arr[i]))
	if n % 2 != 0:
		m.append(abs(arr[n - 1]))
	k = 1
	while k > 0:
		h = max(t)
		l = min(m)
		if l >= h:
			break
		m[m.index(l)] = h
		t[t.index(h)] = l
		k -= 1
	print(sum(m) - sum(t))
for i in range(int(input())):
	func()


for tc in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(a1m, a2m) = (100000000000, 0)
	(a1s, a2s) = (0, 0)
	for i in range(0, n, 2):
		val = abs(arr[i])
		a1s += val
		a1m = min(a1m, val)
	for i in range(1, n, 2):
		val = abs(arr[i])
		a1s -= val
		a2m = max(a2m, val)
	cd = a2m - a1m if a2m > a1m else 0
	print(a1s + 2 * cd)


t = int(input())
for t in range(t):
	n = int(input())
	arr = [abs(int(i)) for i in input().split()]
	minm = arr[0]
	maxm = arr[1]
	j = 0
	k = 1
	for i in range(2, n):
		if (i + 1) % 2 == 1:
			if arr[i] < minm:
				minm = arr[i]
				j = i
		elif arr[i] > maxm:
			maxm = arr[i]
			k = i

	def arr_sum(a):
		sum = 0
		for i in range(len(a)):
			if (i + 1) % 2 == 0:
				sum = sum - arr[i]
			else:
				sum = sum + arr[i]
		return sum
	initial_sum = arr_sum(arr)
	(arr[j], arr[k]) = (arr[k], arr[j])
	final_sum = arr_sum(arr)
	ans = max(initial_sum, final_sum)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	el = 1000000000.0 + 7
	om = -(1000000000.0 + 7)
	summ = 0
	for i in range(n):
		if i % 2 == 0:
			if abs(l[i]) < abs(el):
				el = abs(l[i])
			summ = summ + abs(l[i])
		else:
			if abs(l[i]) > om:
				om = abs(l[i])
			summ = summ - abs(l[i])
	if abs(om) > abs(el):
		summ = summ + 2 * abs(om)
		summ = summ - 2 * abs(el)
	print(summ)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(even, odd) = ([], [])
	for i in range(n):
		if i % 2 == 0:
			even.append(abs(arr[i]))
		else:
			odd.append(abs(arr[i]))
	print(max(sum(even) - sum(odd), sum(even) - min(even) + max(odd) - sum(odd) + max(odd) - min(even)))


for _ in range(int(input())):
	n = int(input())
	l = list(map(lambda x: abs(int(x)), input().split()))
	ps = l[::2]
	ns = l[1::2]
	if min(ps) >= max(ns):
		print(sum(ps) - sum(ns))
	else:
		print(sum(ps) - min(ps) + max(ns) - (sum(ns) + min(ps) - max(ns)))


N = int(input())
for i in range(N):
	n = int(input())
	l = [int(x) for x in input().split()]
	sub1 = []
	sub2 = []
	for i in range(n):
		if i % 2 == 0:
			sub1.append(abs(l[i]))
		else:
			sub2.append(abs(l[i]))
	sum1 = sum(sub1) - sum(sub2)
	min_l = min(sub1)
	max_l = max(sub2)
	if min_l > max_l:
		print(sum1)
	else:
		sum1 += 2 * abs(max_l - min_l)
		print(sum1)


def test():
	n = int(input())
	l = list(map(int, input().split()))
	even = [abs(l[i]) for i in range(0, n, 2)]
	odd = [abs(l[i]) for i in range(1, n, 2)]
	y = sum(even) - sum(odd)
	minx = min(even)
	maxx = max(odd)
	even.remove(minx)
	odd.remove(maxx)
	even.append(maxx)
	odd.append(minx)
	x = sum(even) - sum(odd)
	print(max(x, y))
t = int(input())
for _ in range(t):
	test()


t = int(input())
for _ in range(t):
	n = int(input())
	xlst = list(map(int, input().split()))
	lst = [abs(i) for i in xlst]
	even = [lst[i] for i in range(0, n, 2)]
	odd = [lst[i] for i in range(1, n, 2)]
	y = sum(even) - sum(odd)
	minx = min(even)
	maxx = max(odd)
	even.remove(minx)
	odd.remove(maxx)
	even.append(maxx)
	odd.append(minx)
	x = sum(even) - sum(odd)
	print(max(x, y))


for _ in range(int(input())):
	n = int(input())
	inp = list(map(int, input().split()))
	arr = []
	for i in inp:
		arr.append(abs(i))
	(add, sub) = ([], [])
	for i in range(0, n, 2):
		if i == n - 1:
			add.append(arr[i])
		else:
			add.append(arr[i])
			sub.append(arr[i + 1])
	(add, sub) = (sorted(add), sorted(sub))
	ans = sum(add) - add[0] - (sum(sub) - sub[-1]) + sub[-1] - add[0]
	print(max(ans, sum(add) - sum(sub)))


t = int(input(''))
for _ in range(t):
	n = int(input(''))
	a = list(map(int, input().split()))
	if 2 <= n <= 10 ** 5:
		for i in range(len(a)):
			if a[i] < 0:
				a[i] = a[i] * -1
		ae = a[::2]
		ao = a[1::2]
		ma = max(ao)
		mi = min(ae)
		sum = 0
		for i in range(n):
			if i % 2 == 0:
				sum += a[i]
			else:
				sum -= a[i]
		if ma > mi:
			print(sum + 2 * (ma - mi))
		else:
			print(sum)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	maximum = a[1]
	minimum = a[0]
	mai = 0
	mii = 0
	for i in range(n):
		a[i] = abs(a[i])
	ae = a[::2]
	ao = a[1::2]
	maximum = max(ao)
	minimum = min(ae)
	for i in range(n):
		ans += pow(-1, i) * a[i]
	if maximum > minimum:
		print(ans + 2 * (maximum - minimum))
	else:
		print(ans)


for _ in range(int(input())):
	m = int(input())
	p = list(map(int, input().split()))
	add = p[::2]
	sub = p[1::2]
	max = 0
	min = 99999999999
	for i in range(len(sub)):
		if sub[i] >= 0:
			pass
		else:
			sub[i] = -sub[i]
		if sub[i] > max:
			max = sub[i]
	for i in range(len(add)):
		if add[i] >= 0:
			pass
		else:
			add[i] = -add[i]
		if add[i] < min:
			min = add[i]
	if min > max:
		print(sum(add) - sum(sub))
	else:
		print(sum(add) - sum(sub) - 2 * min + 2 * max)


for _ in range(int(input())):
	num = int(input())
	array = list(map(int, input().split()))
	array = list(map(abs, array))
	even = array[::2]
	odd = array[1::2]
	even_min = min(even)
	odd_max = max(odd)
	if odd_max > even_min:
		total = sum(even) - even_min + odd_max - sum(odd) + odd_max - even_min
	else:
		total = sum(even) - sum(odd)
	print(total)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	for i in range(n):
		arr[i] = abs(arr[i])
	maxeven = arr[1]
	minodd = arr[0]
	mo = 0
	me = 1
	for i in range(2, n):
		if i % 2 == 0:
			if arr[i] < minodd:
				minodd = arr[i]
				mo = i
		elif arr[i] > maxeven:
			maxeven = arr[i]
			me = i
	if arr[mo] < arr[me]:
		(arr[mo], arr[me]) = (arr[me], arr[mo])
	ans = 0
	for i in range(n):
		if i % 2 == 0:
			ans = ans + arr[i]
		else:
			ans = ans - arr[i]
	print(ans)


def solve(arr, n):
	p = []
	m = []
	for i in range(n):
		if i % 2:
			m.append(arr[i])
		else:
			p.append(arr[i])
	if max(m) > min(p):
		return sum(p) - min(p) + max(m) - (sum(m) - max(m) + min(p))
	else:
		return sum(p) - sum(m)
t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	arr = list(map(abs, arr))
	print(solve(arr, n))
	t -= 1


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = []
	y = []
	for i in range(n):
		if i % 2 == 0:
			x.append(abs(l[i]))
		else:
			y.append(abs(l[i]))
	s = max(y)
	h = min(x)
	z = sum(x) - sum(y)
	if h < s:
		z = z + 2 * (s - h)
	print(z)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))[:n]
	for i in range(n):
		if abs(arr[i]) != arr[i]:
			arr[i] = -arr[i]
	evenIndices = arr[0::2]
	oddIndices = arr[1::2]
	minEven = min(evenIndices)
	maxOdd = max(oddIndices)
	z = sum(evenIndices) - sum(oddIndices)
	if maxOdd > minEven:
		z = z + 2 * (maxOdd - minEven)
	print(z)


import sys
for i in range(int(input())):
	n = int(input())
	a = list(map(abs, map(int, sys.stdin.readline().split())))
	a_add = a[::2]
	a_subtract = a[1::2]
	a_max = max(a_subtract)
	a_min = min(a_add)
	s_add = sum(a_add)
	s_sub = sum(a_subtract)
	print(max(s_add - s_sub + 2 * a_max - 2 * a_min, s_add - s_sub))


for i in range(int(input())):
	n = int(input())
	a = list(map(abs, map(int, input().split())))
	a_add = a[::2]
	a_subtract = a[1::2]
	a_max = max(a_subtract)
	a_min = min(a_add)
	print(max(sum(a_add) - sum(a_subtract) + 2 * a_max - 2 * a_min, sum(a_add) - sum(a_subtract)))


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	x = []
	y = []
	for i in range(n):
		if i % 2 == 0:
			x.append(abs(a[i]))
		else:
			y.append(abs(a[i]))
	mx = max(y)
	mn = min(x)
	av = sum(x) - sum(y)
	if mn < mx:
		av = av + 2 * (mx - mn)
	print(av)


for c in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	sub = []
	ad = []
	for i in range(n):
		if i % 2 == 0:
			ad.append(abs(l[i]))
		else:
			sub.append(abs(l[i]))
	x = min(ad)
	y = max(sub)
	res = sum(ad) - sum(sub)
	if x < y:
		res += 2 * (y - x)
	print(res)


n = int(input())
for i in range(n):
	N = int(input())
	l = []
	k = []
	s = input().split(' ')
	for i in range(N):
		s[i] = int(s[i])
		if s[i] < 0:
			s[i] = -s[i]
	for i in range(N):
		if i % 2 == 0:
			l.append(s[i])
		else:
			k.append(s[i])
	mn = max(k)
	mp = min(l)
	if mn > mp:
		print(sum(l) - mp + mn - (sum(k) + mp - mn))
	else:
		print(sum(l) - sum(k))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	subindex = []
	addindex = []
	for i in range(n):
		if i % 2 == 0:
			addindex.append(abs(l[i]))
		else:
			subindex.append(abs(l[i]))
	x = min(addindex)
	y = max(subindex)
	ans = sum(addindex) - sum(subindex)
	if x < y:
		ans += 2 * (y - x)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	j = []
	for i in a:
		if i < 0:
			j.append(-i)
		else:
			j.append(i)
	even = []
	for i in range(0, n, 2):
		even.append(j[i])
	odd = []
	for m in range(1, n, 2):
		odd.append(j[m])
	if min(even) < max(odd):
		m = min(even)
		j = max(odd)
		(even[even.index(m)], odd[odd.index(j)]) = (j, m)
	print(sum(even) - sum(odd))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	le = [abs(l[i]) for i in range(0, n, 2)]
	lo = [abs(l[i]) for i in range(1, n, 2)]
	a = sum(le) - sum(lo) - 2 * min(le) + 2 * max(lo)
	an = sum(le) - sum(lo)
	print(max(a, an))


t = int(input())
for _ in range(t):
	n = int(input())
	s = 0
	o_min = 10 ** 10
	e_max = -1
	arr = list(map(int, input().split()))
	for i in range(1, n + 1):
		a = abs(arr[i - 1])
		mul = (-1) ** (i - 1)
		if i % 2 == 0 and a > e_max:
			e_max = a
		elif i % 2 == 1 and a < o_min:
			o_min = a
		s += mul * a
	if o_min < e_max:
		s += 2 * (e_max - o_min)
	print(s)


import sys
t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	l1 = []
	l2 = []
	for i in range(0, n):
		if i % 2 == 0:
			l1.append(abs(arr[i]))
		else:
			l2.append(abs(arr[i]))
	s1 = sum(l1) - sum(l2)
	s2 = sum(l1) - min(l1) + max(l2) - (sum(l2) - max(l2) + min(l1))
	print(max(s1, s2))
	t -= 1


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	l2 = []
	for i in range(n):
		if i % 2 == 0:
			l1.append(abs(l[i]))
		else:
			l2.append(abs(l[i]))
	s1 = sum(l1)
	s2 = sum(l2)
	p = s1 - s2
	l1.sort()
	l2.sort()
	s1 = s1 - l1[0] + l2[-1]
	s2 = s2 - l2[-1] + l1[0]
	q = s1 - s2
	if p > q:
		print(p)
	else:
		print(q)


n = int(input())
for i in range(n):
	n = int(input())
	a = list(map(int, input().split()))
	maxi = -1000000000000000000000000000000
	mini = 10000000000000000000000000000000
	b = []
	c = []
	turn = 0
	for i in a:
		if turn == 0:
			b.append(abs(i))
			turn = 1
		else:
			c.append(abs(i))
			turn = 0
	n_b = sum(b) - min(b) + max(c)
	n_c = sum(c) - max(c) + min(b)
	ans = n_b - n_c
	ans = max(sum(b) - sum(c), ans)
	print(ans)


from collections import Counter, defaultdict
from math import *
for _ in range(int(input())):
	n = int(input())
	a = [abs(int(x)) for x in input().split()]
	M = 0
	Mind = 1
	m = float('inf')
	mind = 0
	for i in range(n):
		if i & 1 and M < a[i]:
			M = a[i]
			Mind = i
		elif i % 2 == 0 and m > a[i]:
			m = a[i]
			mind = i
	sumT = lambda a: sum(a[::2]) - sum(a[1::2])
	sum1 = sumT(a)
	(a[mind], a[Mind]) = (a[Mind], a[mind])
	print(max(sum1, sumT(a)))


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	maxvalsubtracted = sum_ = 0
	minvaladded = float('inf')
	for i in range(len(A)):
		if i % 2 == 0:
			minvaladded = min(abs(A[i]), minvaladded)
			sum_ += abs(A[i])
		else:
			maxvalsubtracted = max(abs(A[i]), maxvalsubtracted)
			sum_ -= abs(A[i])
	print(max(sum_ + 2 * maxvalsubtracted - 2 * minvaladded, sum_))


tc = int(input())
for _ in range(tc):
	n = int(input())
	arr = [int(x) for x in input().split(' ')]
	mini = abs(arr[0])
	maxi = abs(arr[1])
	even_sum = 0
	odd_sum = 0
	for i in range(n):
		if i % 2 == 0:
			even_sum += abs(arr[i])
			if abs(arr[i]) < mini:
				mini = abs(arr[i])
		else:
			odd_sum += abs(arr[i])
			if abs(arr[i]) > maxi:
				maxi = abs(arr[i])
	if mini > maxi:
		print(even_sum - odd_sum)
	else:
		print(even_sum - odd_sum - 2 * mini + 2 * maxi)


for _ in range(int(input())):
	v = int(input())
	m = list(map(int, input().split()))
	even = []
	odd = []
	for i in m[::2]:
		even.append(abs(i))
	for j in m[1::2]:
		odd.append(abs(j))
	print(max(sum(even) - sum(odd) - 2 * min(even) + 2 * max(odd), sum(even) - sum(odd)))


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	even = []
	odd = []
	for i in A[::2]:
		even.append(abs(i))
	for j in A[1::2]:
		odd.append(abs(j))
	print(max(sum(even) - sum(odd) - 2 * min(even) + 2 * max(odd), sum(even) - sum(odd)))


import math
T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	A = list(map(abs, A))
	AO = []
	AE = []
	SO = 0
	SE = 0
	for j in range(N):
		if j % 2 == 0:
			AO.append(A[j])
			SO = SO + A[j]
		else:
			AE.append(A[j])
			SE = SE + A[j]
	AO.sort()
	AE.sort()
	S = SO - SE - 2 * AO[0] + 2 * AE[len(AE) - 1]
	S = max(S, SO - SE)
	print(S)


t = input()
for c in range(0, int(t)):
	n = int(input())
	A = list(map(int, input().split()))
	odd = [abs(a) for a in A[1::2]]
	even = [abs(a) for a in A[::2]]
	print(max(sum(even) - sum(odd) - 2 * min(even) + 2 * max(odd), sum(even) - sum(odd)))


get_int = lambda : int(input())
get_mint = lambda : list(map(int, input().split()))
for _ in range(get_int()):
	N = get_int()
	A = get_mint()
	odd = [abs(a) for a in A[1::2]]
	even = [abs(a) for a in A[::2]]
	print(max(sum(even) - sum(odd) - 2 * min(even) + 2 * max(odd), sum(even) - sum(odd)))


def arraygen(a, e):
	ls = list(map(abs, a))
	b = ls[0]
	c = ls[1]
	for x in range(0, e, 2):
		if ls[x] < b:
			b = ls[x]
	for y in range(1, e, 2):
		if ls[y] > c:
			c = ls[y]
	sumz = 0
	for x in range(e):
		sumz += (-1) ** x * ls[x]
	return max(sumz, sumz - 2 * b + 2 * c)
d = int(input())
for x in range(d):
	e = int(input())
	f = list(map(int, input().split()))
	print(arraygen(f, e))


t = int(input())
while t != 0:
	n = int(input())
	x = list(map(int, input().split()))
	a = list(map(lambda b: abs(b), x))
	pos = []
	neg = []
	for i in range(len(a)):
		if i % 2 == 0:
			pos.append(a[i])
		else:
			neg.append(a[i])
	if max(neg) > min(pos):
		print(sum(pos) - sum(neg) + (max(neg) - min(pos)) * 2)
	else:
		print(sum(pos) - sum(neg))
	t -= 1


t = int(input())
while t:
	t -= 1
	(li1, li2) = ([], [])
	n = int(input())
	li = list(map(int, input().split()))
	for i in range(n):
		if i % 2 == 0:
			li1.append(abs(li[i]))
		else:
			li2.append(abs(li[i]))
	if min(li1) >= max(li2):
		print(sum(li1) - sum(li2))
	else:
		print(sum(li1) - min(li1) + max(li2) - (sum(li2) - max(li2) + min(li1)))


for _ in range(int(input())):
	n = int(input())
	l1 = [abs(int(x)) for x in input().split()]
	min = l1[0]
	max = l1[1]
	idx = 1
	ldx = 0
	for i in range(3, n, 2):
		if max < l1[i]:
			max = l1[i]
			idx = i
	for i in range(2, n, 2):
		if min > l1[i]:
			min = l1[i]
			ldx = i
	if l1[idx] > l1[ldx]:
		(l1[idx], l1[ldx]) = (l1[ldx], l1[idx])
	sum = 0
	for i in range(n):
		if i % 2 == 0:
			sum = sum + l1[i]
		elif i % 2 != 0:
			sum = sum - l1[i]
	print(sum)


t = int(input())
for i in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	odd = [abs(ar[x]) for x in range(1, n, 2)]
	even = [abs(ar[x]) for x in range(0, n, 2)]
	maxo = max(odd)
	mine = min(even)
	if maxo > mine:
		indo = odd.index(maxo)
		inde = even.index(mine)
		(odd[indo], even[inde]) = (even[inde], odd[indo])
	print(sum(even) - sum(odd))


for _ in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split(' ')))
	ls = list(map(abs, ls))
	ls_odd = [ls[i] for i in range(len(ls)) if (i + 1) % 2 != 0]
	ls_even = [ls[i] for i in range(len(ls)) if (i + 1) % 2 == 0]
	if max(ls_even) > min(ls_odd):
		print(sum(ls_odd) - sum(ls_even) + 2 * max(ls_even) - 2 * min(ls_odd))
	else:
		print(sum(ls_odd) - sum(ls_even))


from sys import stdin, stdout
stdint = lambda : int(stdin.readline())
seq = lambda : list(map(int, stdin.readline().strip().split()))
for _ in range(stdint()):
	n = stdint()
	nums = seq()
	total = 0
	minVal = abs(nums[0])
	total += abs(nums[0])
	maxVal = abs(nums[1])
	total -= abs(nums[1])
	for i in range(2, n):
		if i % 2 == 0:
			if minVal > abs(nums[i]):
				minVal = abs(nums[i])
			total += abs(nums[i])
		else:
			if maxVal < abs(nums[i]):
				maxVal = abs(nums[i])
			total -= abs(nums[i])
	if minVal < maxVal:
		print(total - 2 * minVal + 2 * maxVal)
	else:
		print(total)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	maxi = 0
	mini = 0
	add = []
	sub = []
	for i in range(0, n):
		if i % 2 == 0:
			add.append(abs(a[i]))
		else:
			sub.append(abs(a[i]))
	for i in range(len(add)):
		if add[mini] > add[i]:
			mini = i
	for i in range(len(sub)):
		if sub[maxi] < sub[i]:
			maxi = i
	if add[mini] < sub[maxi]:
		(add[mini], sub[maxi]) = (sub[maxi], add[mini])
	count = 0
	for i in add:
		count += i
	for i in sub:
		count -= i
	print(count)


for _ in range(int(input())):
	size = int(input())
	array = list(map(int, input().split()))
	max_odd_index = None
	for index in range(1, size, 2):
		if max_odd_index == None or abs(array[index]) > abs(array[max_odd_index]):
			max_odd_index = index
	min_even_index = None
	for index in range(0, size, 2):
		if min_even_index == None or abs(array[index]) < abs(array[min_even_index]):
			min_even_index = index
	if abs(array[max_odd_index]) > abs(array[min_even_index]):
		temp = array[max_odd_index]
		array[max_odd_index] = array[min_even_index]
		array[min_even_index] = temp
	result = 0
	for index in range(size):
		if index % 2 == 0:
			result += abs(array[index])
		else:
			result -= abs(array[index])
	print(result)


for _ in range(int(input())):
	n = int(input())
	a = [abs(int(x)) for x in input().split()]
	pos = a[::2]
	neg = a[1::2]
	if max(neg) < min(pos):
		print(sum(pos) - sum(neg))
	else:
		print(sum(pos) - sum(neg) + 2 * (max(neg) - min(pos)))


import math
for i in range(int(input())):
	a = int(input())
	lis = list(map(int, input().split()))
	max = 1
	for i in range(1, a, 2):
		if abs(lis[i]) > abs(lis[max]):
			max = i
	min = 0
	for i in range(0, a, 2):
		if abs(lis[i]) < abs(lis[min]):
			min = i
	if abs(lis[max]) > abs(lis[min]):
		temp = lis[min]
		lis[min] = lis[max]
		lis[max] = temp
	tot = 0
	for i in range(a):
		if i % 2 == 0:
			tot += abs(lis[i])
		else:
			tot -= abs(lis[i])
	print(tot)


for i in range(int(input())):
	no = int(input())
	li = list(map(abs, map(int, input().split())))
	l1 = li[::2]
	l2 = li[1::2]
	min1 = min(l1)
	max1 = max(l2)
	if max1 > min1:
		sum1 = sum(l1) - min1 + max1 - (sum(l2) - max1 + min1)
	else:
		sum1 = sum(l1) - sum(l2)
	print(sum1)


for i in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	listp = []
	listm = []
	j = 0
	sum1 = 0
	while j < n:
		if j % 2 == 0:
			listp.append(abs(list1[j]))
		else:
			listm.append(abs(list1[j]))
		j += 1
	sum1 += sum(listp) - sum(listm)
	sum2 = sum1 + 2 * (max(listm) - min(listp))
	if sum1 > sum2:
		print(sum1)
	else:
		print(sum2)


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	(oddSum, evenSum) = (0, 0)
	(maxEven, minOdd) = (float('-inf'), float('inf'))
	for i in range(n):
		if (i + 1) % 2 != 0:
			oddSum += abs(lst[i])
			minOdd = min(minOdd, abs(lst[i]))
		else:
			evenSum += abs(lst[i])
			maxEven = max(maxEven, abs(lst[i]))
	ans1 = oddSum - evenSum
	ans2 = oddSum - evenSum + 2 * (maxEven - minOdd)
	print(max(ans1, ans2))


for _ in range(int(input())):
	n = int(input())
	num = [abs(int(x)) for x in input().split()]
	(l, h) = (10 ** 9 + 1, -10 ** 9 - 1)
	sum1 = sum2 = 0
	for i in range(0, n, 2):
		x = num[i]
		sum1 += x
		if x < l:
			l = x
	for j in range(1, n, 2):
		y = num[j]
		sum2 += y
		if y > h:
			h = y
	s = sum1 - sum2
	r = s + 2 * h - 2 * l
	if s > r:
		r = s
	print(r)


import math
for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	(mx, mn) = (-math.inf, math.inf)
	lst1 = []
	lst2 = []
	i = 0
	while i < len(lst):
		if i % 2 == 0:
			lst1.append(abs(lst[i]))
		else:
			lst2.append(abs(lst[i]))
		i += 1
	sum1 = sum(lst1) - sum(lst2)
	sum2 = sum1 + 2 * (max(lst2) - min(lst1))
	if sum1 > sum2:
		print(sum1)
	else:
		print(sum2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(minno, maxno) = (float('inf'), float('-inf'))
	(f, s) = (0, 0)
	for i in range(n):
		if i % 2 == 0:
			f += abs(a[i])
			minno = min(abs(a[i]), minno)
		else:
			s -= abs(a[i])
			maxno = max(maxno, abs(a[i]))
	if maxno > minno:
		f = f + maxno - minno
		s = s + maxno - minno
	print(f + s)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(min_pos, max_ne) = (1000000000, -1000000000)
	total_sum = 0
	for i in range(n):
		v = abs(l[i])
		if i % 2 == 0:
			total_sum = total_sum + v
			min_pos = min(min_pos, v)
		else:
			total_sum = total_sum - v
			max_ne = max(max_ne, v)
	swap_sum = total_sum + 2 * max_ne - 2 * min_pos
	print(max(total_sum, swap_sum))