You are given an array of $n$ integers $a_1, a_2, \ldots, a_n$. The integers are either $1$ or $-1$. You have to perform the following operation exactly once on the array $a$:

Choose an index $i$ ($1 \leq i < n$) and flip the signs of $a_i$ and $a_{i+1}$. Here, flipping the sign means $-1$ will be $1$ and $1$ will be $-1$.

What is the maximum possible value of $a_1 + a_2 + \ldots + a_n$ after applying the above operation?


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 10^5$), the length of the array $a$.

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($a_i = 1$ or $a_i = -1$).

The sum of $n$ over all cases doesn't exceed $10^5$.


-----Output-----

For each test case, print the maximum possible sum of the array $a$ you can get in a separate line.


-----Examples-----

Input
4
5
-1 1 1 -1 -1
5
1 1 -1 -1 -1
2
1 1
4
1 -1 -1 1
Output
3
3
-2
4


-----Note-----

In the first case, we can choose index $4$ and flip the signs of $a_4$ and $a_5$. After this operation, the sum will be $-1+1+1+1+1 = 3$. We can't make the sum larger than this.

In the third case, the only option is to choose the index $1$.

Difficulty: EASY
Tags: Implementation

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
t = int(input())
result = []
for i in range(t):
	n = int(input())
	ai = list(map(int, input().split(' ')))
	s = sum(ai)
	h = False
	for j in range(n - 1):
		if (ai[j] == -1) & (ai[j + 1] == -1):
			h = True
			result.append(s + 4)
			break
	if h == False:
		if ai.count(-1) == 0:
			result.append(s - 4)
		else:
			result.append(s)
for i in result:
	print(i)


for i in range(int(input())):
	int(input())
	a = input()
	s = list(map(int, a.split()))
	if a.count('-1 -1') > 0:
		print(sum(s) + 4)
	elif a.count('-1 1') > 0 or a.count('1 -1') == 1:
		print(sum(s))
	else:
		print(sum(s) - 4)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d1 = True
	d2 = True
	for k in range(n - 1):
		if a[k] == -1 and a[k + 1] == -1:
			a[k] = 1
			a[k + 1] = 1
			d1 = False
			d2 = False
			print(sum(a))
			break
	if d1:
		for k in range(n - 1):
			if a[k] == -1 and a[k + 1] == 1:
				a[k] = 1
				a[k + 1] = -1
				d2 = False
				print(sum(a))
				break
			elif a[k] == 1 and a[k + 1] == -1:
				a[k] = -1
				a[k + 1] = 1
				d2 = False
				print(sum(a))
				break
	if d2:
		a[0] = -1
		a[1] = -1
		print(sum(a))


test = int(input())
for _ in range(test):
	length = int(input())
	nums = list(map(int, input().split()))
	total = sum(nums)
	maximum = nums.count(1)
	if length == 2:
		print(-1 * nums[0] + -1 * nums[1])
	else:
		left = 0
		right = 1
		if total == nums.count(1):
			print(total - 4)
		else:
			while right < length:
				if nums[left] == nums[right] and nums[left] == -1:
					total += 4
					break
				left += 1
				right += 1
			print(total)


import sys
sys.setrecursionlimit(10 ** 9)

def m(L):
	F = True
	for i in range(len(L) - 1):
		if L[i] == -1 and L[i + 1] == -1:
			F = False
			return sum(L) + 4
	if F:
		if sum(L) == len(L):
			return len(L) - 4
	return sum(L)
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(m(l))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	flag = 0
	for j in range(n):
		if j <= n - 2:
			if l[j] == -1 and l[j + 1] == -1:
				print(sum(l) + 4)
				flag = 1
				break
	if flag == 0:
		if -1 in l:
			print(sum(l))
		else:
			print(sum(l) - 4)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	s = sum(arr)
	if s == len(arr):
		s -= 4
	else:
		for i in range(len(arr) - 1):
			if arr[i] == -1:
				if arr[i + 1] == -1:
					s += 4
					break
	print(s)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	s = sum(arr)
	plus = -4
	for a in arr:
		if a < 0:
			plus = 0
			break
	for i in range(1, n):
		if arr[i] < 0 and arr[i - 1] < 0:
			plus = 4
			break
	print(s + plus)


for _ in range(int(input())):
	n = int(input())
	a = input()
	c = list(map(int, a.split(' ')))
	if '-1 -1' in a:
		print(sum(c) + 4)
	elif '-' not in a:
		print(sum(c) - 4)
	else:
		print(sum(c))


def solution(n, a: list):
	sm = sum(a)
	flag_two_minus = False
	flag_minus_plus = False
	for i in range(n - 1):
		if a[i] + a[i + 1] == 0:
			flag_minus_plus = True
		if a[i] < 0 and a[i + 1] < 0:
			flag_two_minus = True
			break
	if flag_two_minus:
		return sm + 4
	elif flag_minus_plus:
		return sm
	return sm - 4
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(solution(n, a))


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	flag = 0
	for i in range(n - 1):
		if l[i] == -1 and l[i + 1] == -1:
			flag = 1
			break
	if flag == 0:
		flag2 = 0
		for i in range(n - 1):
			if l[i] == -1 and l[i + 1] == 1 or (l[i] == 1 and l[i + 1] == -1):
				flag2 = 1
				break
		if flag2 == 0:
			print(s - 4)
		else:
			print(s)
	else:
		print(s + 4)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))
	f = False
	for i in range(n - 1):
		if a[i] == a[i + 1] and a[i] == -1:
			a[i] = -1 * a[i]
			a[i + 1] = -1 * a[i + 1]
			f = True
			print(sum(a))
			break
	if not f:
		for i in range(n):
			if a[i] != 1:
				print(sum(a))
				break
		else:
			print(sum(a) - 4)


t = int(input())
for i in range(t):
	n = int(input())
	m = False
	a = list(map(int, input().split()))
	for i in range(n - 1):
		if a[i] == -1:
			if a[i + 1] == -1:
				a[i] = 1
				a[i + 1] = 1
				m = True
				break
	if m == True:
		print(sum(a))
	else:
		t = False
		for i in range(n - 1):
			if a[i] != a[i + 1]:
				a[i] = -a[i]
				a[i + 1] = -a[i + 1]
				t = True
				break
		if t == True:
			print(sum(a))
		else:
			a[0] = -a[0]
			a[1] = -a[1]
			print(sum(a))


def flipFlopSum(array, length):
	negative = False
	Sum = sum(array)
	for i in range(length - 1):
		if array[i] == array[i + 1] == -1:
			array[i] = array[i + 1] = 1
			print(Sum + 4)
			return
		elif array[i] == -1 or array[i + 1] == -1:
			negative = True
	if negative:
		print(Sum)
	else:
		print(Sum - 4)
testcases = int(input())
arrays = []
for _ in range(testcases):
	length = int(input())
	arrays.append([length, list(map(int, input().split()))])
for (length, array) in arrays:
	flipFlopSum(array, length)


def check(arr, k):
	out = sum(arr)
	for i in range(k - 1):
		if arr[i] == -1 and arr[i + 1] == -1:
			return out + 4
			break
	if out == len(arr):
		return out - 4
	else:
		return out
n = int(input())
for _ in range(n):
	k = int(input())
	arr = list(map(int, input().split()))
	print(check(arr, k))


def f():
	h = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	for i in range(1, len(a)):
		if a[i] == -1 and a[i - 1] == -1:
			print(s + 4)
			return
	for i in range(len(a)):
		if a[i] == -1:
			print(s)
			return
	print(s - 4)
n = int(input())
for test in range(n):
	f()


t = int(input())
res = []
for _ in range(t):
	done = False
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(1, n):
		if a[i] == -1 and a[i - 1] == -1:
			a[i] = 1
			a[i - 1] = 1
			done = True
			break
	if not done:
		for i in range(1, n):
			if a[i] == -1 and a[i - 1] == 1:
				done = True
				break
			if a[i] == 1 and a[i - 1] == -1:
				done = True
				break
	if not done:
		a[0] = -1
		a[1] = -1
	res.append(sum(a))
for i in res:
	print(i)


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	t = 0
	for i in range(len(nums) - 1):
		if nums[i] == -1 and nums[i + 1] == -1:
			nums[i] = 1
			nums[i + 1] = 1
			t = 1
			break
		elif nums[i] == -1 and nums[i + 1] == 1 or (nums[i] == 1 and nums[i + 1] == -1):
			continue
	if t == 0:
		if all((i == 1 for i in nums)):
			nums[0] = -1
			nums[1] = -1
		elif all((i == -1 for i in nums)):
			nums[0] = 1
			nums[1] = 1
	print(sum(nums))


def program():
	n = int(input())
	a = [int(x) for x in input().split()]
	record = -1
	for i in range(len(a) - 1):
		if a[i] == -1 and a[i + 1] == -1:
			a[i] = 1
			a[i + 1] = 1
			record = -2
			break
		elif a[i] == 1 and a[i + 1] == -1 or (a[i] == -1 and a[i + 1] == 1):
			record = i
	else:
		if record != -2 and record != -1:
			if a[record] == 1:
				a[record] = -1
				a[record + 1] = 1
			else:
				a[record] = 1
				a[record + 1] = -1
		elif record == -1:
			a[0] = -1
			a[1] = -1
	return sum(a)
t = int(input())
for i in range(t):
	print(program())


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if arr.count(-1) >= 2:
		for i in range(n):
			if i + 1 < n and arr[i] == arr[i + 1] and (arr[i] == -1):
				arr[i] = 1
				arr[i + 1] = 1
				break
		print(sum(arr))
	elif arr.count(-1) == 0:
		print(sum(arr) - 4)
	else:
		print(sum(arr))


t = int(input())
for i in range(t):
	n = int(input())
	L = list(map(int, input().split()))
	sum = 0
	x = -L.count(-1)
	y = L.count(1)
	ans = False
	for i in range(len(L) - 1):
		if L[i] == -1 and L[i + 1] == -1:
			ans = True
			break
	if x == 0 and y != 0:
		print(y - 4)
	elif y == 0 and x != 0:
		print(x + 4)
	elif x == 0 and y == 0:
		print(0)
	elif ans == False:
		print(x + y)
	else:
		print(x + y + 4)


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

def solve(number, array):
	ans = sum(array)
	for i in range(0, number - 1):
		if array[i] == array[i + 1] == -1:
			ans += 4
			return ans
	for i in range(0, number - 1):
		if array[i] == -1 * array[i + 1]:
			return ans
	for i in range(0, number - 1):
		if array[i] == array[i + 1] == 1:
			return ans - 4
test_case = int(input())
for _ in range(test_case):
	num = int(input())
	arr = input_list()
	print(solve(num, arr))


for _ in range(int(input())):
	n = int(input())
	num = list(map(int, input().split()))
	x = 0
	flag = False
	result = sum(num)
	for i in range(1, n):
		if num[x] == -1 and num[i] == -1:
			result += 4
			flag = True
			break
		if num[x] == -1:
			flag = True
		x += 1
	if num[x] == -1:
		flag = True
	if flag:
		print(result)
	else:
		print(result - 4)


t = int(input())
for _ in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	s = 0
	sm = sum(x)
	p = 0
	d = True
	for i in x[0:n - 1]:
		if i == -1:
			s += i
			p = 1
		else:
			s = 0
		if s == -2:
			print(sm + 4)
			d = False
			break
	if x[n - 1] == -1:
		s += -1
		p = 1
	if d == True:
		if s == -2:
			print(sm + 4)
		elif p == 1:
			print(sm)
		else:
			print(sm - 4)


for _ in range(int(input())):
	n = int(input())
	a = [int(no) for no in input().split(' ')]
	s1 = sum(a)
	c = 0
	d = 0
	e = 0
	for i in range(len(a) - 1):
		if a[i] == -1 and a[i + 1] == -1:
			c = 1
			break
		elif a[i] == 1 and a[i + 1] == 1:
			d = 1
		else:
			e = 1
	if c > 0:
		print(s1 + 4)
	elif e > 0:
		print(s1)
	else:
		print(s1 - 4)


t = int(input())
for p in range(t):
	n = int(input())
	s = input()
	l = list(map(int, s.split()))
	if '-1 -1' in s:
		print(sum(l) + 4)
	elif '-1' in s:
		print(sum(l))
	else:
		print(sum(l) - 4)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))
	if a.count(-1) == 0:
		a[0] = -1
		a[1] = -1
		print(sum(a))
	elif a.count(-1) == 1:
		x = a.index(-1)
		a[x - 1] = 1
		a[x] = -1
		print(sum(a))
	else:
		flag = True
		for j in range(1, len(a)):
			if a[j] == -1 and a[j - 1] == -1:
				a[j] = 1
				a[j - 1] = 1
				flag = False
				print(sum(a))
				break
			else:
				continue
		if flag:
			print(sum(a))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	f = g = 0
	k = 0
	for i in range(len(a) - 1):
		if a[i] == a[i + 1] == -1:
			f = 1
			break
	if f:
		print(sum(a) + 4)
	elif sum(a) == n:
		print(sum(a) - 4)
	else:
		print(sum(a))


a = int(input())
for i in range(a):
	b = int(input())
	c = list(map(int, input().split()))
	if c.count(-1) == 0:
		print(sum(c) - 4)
	else:
		for d in range(b - 1):
			if c[d] == -1 and c[d + 1] == -1:
				print(sum(c) + 4)
				break
		else:
			print(sum(c))


for _ in range(int(input())):
	p = int(input())
	t = list(map(int, input().split()))
	lst = []
	mini = 0
	f1 = 0
	raz = 0
	for i in range(1, p):
		if t[i] < 0 and t[i - 1] < 0:
			t[i] = 1
			t[i - 1] = 1
			mini = 1
			break
		if t[i - 1] < 0 and t[i] > 0:
			f1 = 1
		if t[i - 1] > 0 and t[i] < 0:
			f1 = 1
	if f1 == 0 and mini == 0:
		t[0] = -1
		t[1] = -1
		print(sum(t))
	elif mini == 1:
		print(sum(t))
	else:
		print(sum(t))


t = int(input())
for i in range(t):
	n = int(input())
	mas = list(map(int, input().split()))[:n]
	if n == sum(mas):
		print(sum(mas) - 4)
	else:
		for j in range(len(mas) - 1):
			if mas[j] + mas[j + 1] == -2:
				(mas[j], mas[j + 1]) = (1, 1)
				break
		print(sum(mas))


for _ in range(int(input())):
	n = int(input())
	a = input()
	lst = list(map(int, a.split()))
	if a.find('-1 -1') != -1:
		print(sum(lst) + 4)
	elif a.find('-1 1') != -1 or a.find('1 -1') != -1:
		print(sum(lst))
	else:
		print(sum(lst) - 4)


def sum(arr):
	sum1 = 0
	for i in arr:
		sum1 = sum1 + i
	return sum1

def ques():
	sum1 = 0
	t = int(input())
	while t > 0:
		n = int(input())
		ans = list()
		nums = list(map(int, input().split()))
		s = 0
		for i in range(n - 1):
			if nums[i] == -1 and nums[i + 1] == -1:
				s = 1
				break
			elif nums[i] == -1 and nums[i + 1] == 1 or (nums[i] == 1 and nums[i + 1] == -1):
				s = 2
		if s == 1:
			ans = sum(nums) + 4
		elif s == 2:
			ans = sum(nums)
		else:
			ans = sum(nums) - 4
		print(ans)
		t -= 1
ques()


t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	if -1 not in arr:
		arr[0] = -1
		arr[1] = -1
		print(sum(arr))
	elif 1 not in arr:
		arr[0] = 1
		arr[1] = 1
		print(sum(arr))
	else:
		flag = 0
		for i in range(n - 1):
			if arr[i] == -1 and arr[i + 1] == -1:
				arr[i] = 1
				arr[i + 1] = 1
				flag = 1
				break
		if flag == 1:
			print(sum(arr))
		else:
			print(sum(arr))
	t = t - 1


t = int(input())
for i in range(t):
	num = int(input())
	ind = list(map(int, input().split()))
	result = 0
	res = sum(ind)
	if res == num:
		print(num - 4)
		result = 1
	for j in range(0, num - 1):
		if ind[j] == ind[j + 1] == -1:
			ind[j] = ind[j + 1] = 1
			break
	if result == 0:
		print(sum(ind))


def main():
	n = int(input())
	v = list(map(int, input().split()))
	tot = sum(v)
	print(tot + 4 if any((a == -1 and b == -1 for (a, b) in zip(v, v[1:]))) else tot - 4 if tot == n else tot)
t = int(input())
for _ in range(t):
	main()


for s in [*open(0)][2::2]:
	a = (*map(int, s.split()),)
	print(sum(a) + 4 * ('-1 -1' in s or -({1, -1} > {*a})))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if -1 not in a:
		print(sum(a) - 4)
	else:
		for i in range(1, n):
			if a[i - 1] == -1 and a[i] == -1:
				print(sum(a) + 4)
				break
		else:
			print(sum(a))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	input()
	a = list(map(int, input().split()))
	for i in range(1, len(a)):
		if -1 == a[i] == a[i - 1]:
			print(sum(a) + 4)
			break
	else:
		if -1 in a:
			print(sum(a))
		else:
			print(sum(a) - 4)


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	s = sum(arr)
	if s == n:
		s = s - 4
	else:
		for j in range(n - 1):
			if arr[j] == -1 and arr[j + 1] == -1:
				s = s + 4
				break
	print(s)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	k = 0
	for i in range(n - 1):
		if l[i] == -1:
			k = 2
			if l[i + 1] == -1:
				k = 1
				break
		elif l[i] == 1:
			if l[i + 1] == -1:
				k = 2
	if k == 1:
		print(sum(l) + 4, end='\n')
	elif k == 2:
		print(sum(l), end='\n')
	else:
		print(sum(l) - 4, end='\n')


for s in [*open(0)][2::2]:
	a = (*map(int, s.split()),)
	print(sum(a) - 2 * min(map(sum, zip(a, a[1:]))))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	pos = a.count(1)
	neg = a.count(-1)
	if neg == 0:
		print(pos - 4)
	else:
		for i in range(n - 1):
			if a[i] == -1 and a[i + 1] == -1:
				pos += 2
				neg -= 2
				break
		print(pos - neg)


t = int(input())
B = []
for i in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	if sum(A) == n:
		B.append(sum(A) - 4)
	else:
		for i in range(n - 1):
			if A[i] == -1 and A[i + 1] == -1:
				A[i] = A[i] * -1
				A[i + 1] = A[i + 1] * -1
				break
		suma = sum(A)
		B.append(suma)
for i in B:
	print(i)


for t in range(int(input())):
	n = int(input())
	numbers = list(map(int, input().split()))
	if n == 2:
		print(-sum(numbers))
	elif -1 not in numbers:
		print(sum(numbers) - 4)
	else:
		for i in range(n):
			if i < n - 1 and numbers[i] == -1 and (numbers[i + 1] == -1):
				numbers[i] = numbers[i + 1] = 1
				break
		print(sum(numbers))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	ans = 'NO'
	for j in range(n - 1):
		if a[j] == -1 and a[j + 1] == -1:
			ans = 'YES'
			break
	if ans == 'YES':
		print(sum(a) + 4)
	elif -1 in a:
		print(sum(a))
	else:
		print(sum(a) - 4)


for _ in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	c = 0
	for i in range(a - 1):
		if l[i] == -1 and l[i + 1] == -1:
			c = 1
			break
		elif l[i] == -1 and l[i + 1] == 1 or (l[i] == 1 and l[i + 1] == -1):
			c = 2
	s = sum(l)
	if c == 1:
		print(s + 4)
	elif c == 2:
		print(s)
	else:
		print(s - 4)


n = int(input())
for _ in range(n):
	k = int(input())
	l = list(map(int, input().split()))
	if k == sum(l):
		print(k - 4)
		continue
	m = -1
	c = 0
	for i in range(k - 1):
		if l[i] == -1 and l[i + 1] == -1:
			l[i] = 1
			l[i + 1] = 1
			break
	print(sum(l))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	o = 0
	oo = 0
	s = sum(a)
	for i in range(n - 1):
		if a[i] == -1 and a[i + 1] == -1:
			o = 1
			break
		elif a[i] == -1 and a[i + 1] or (a[i] == 1 and a[i + 1] == -1):
			o = 2
	if o == 1:
		print(s + 4)
	elif o == 2:
		print(s)
	else:
		print(s - 4)


def solve(arr):
	for i in range(1, len(arr)):
		if arr[i] == arr[i - 1] == -1:
			return sum(arr) + 4
	for i in range(1, len(arr)):
		if arr[i] != arr[i - 1]:
			return sum(arr)
	return sum(arr) - 4

def main():
	ans = []
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		ans.append(solve(arr))
	print(*ans, sep='\n')
main()


import math
k = int(input())
for q in range(k):
	n = int(input())
	a = list(map(int, input().split()))
	if sum(a) == n:
		print(n - 4)
	else:
		flag = 0
		for i in range(n - 1):
			if a[i] == -1 and a[i + 1] == -1:
				print(sum(a) + 4)
				flag = 1
				break
		if flag == 0:
			print(sum(a))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = sum(l)
	if x == n:
		print(n - 4)
	else:
		for i in range(n):
			if i != n - 1:
				if l[i] == -1 and l[i + 1] == -1:
					x += 4
					break
		print(x)


def pairwise_sum(liste):
	min = 3
	for i in range(1, len(liste)):
		if liste[i - 1] + liste[i] < min:
			min = liste[i - 1] + liste[i]
		if min == -2:
			break
	if min == -2:
		return sum(liste) + 4
	elif min == 0:
		return sum(liste)
	else:
		return sum(liste) - 4
days = int(input())
for i in range(days):
	length = int(input())
	test = list(map(int, input().split(' ')))
	print(pairwise_sum(test))


def negatives(a):
	x = 0
	y = 1
	for i in range(len(a) - 1):
		if a[x] == '-1' and a[y] == '-1':
			sum = 0
			for i in a:
				sum += int(i)
			print(sum + 4)
			break
		else:
			x += 1
			y += 1
	if y == len(a):
		if '-1' not in a:
			sum = 0
			for i in a:
				sum += int(i)
			print(sum - 4)
		elif '-1' in a:
			sum = 0
			for i in a:
				sum += int(i)
			print(sum)
t = int(input())
for i in range(t):
	c = int(input())
	a = input().split()
	if len(a) == c:
		negatives(a)


for t in range(int(input())):
	n = int(input())
	l = []
	l = list(map(int, input().split(' ')))
	count = 0
	for i in range(n):
		if count == 0 and l[i] == -1:
			count = 1
		elif count == 1 and l[i] == -1 and (l[i - 1] == -1):
			count = 2
			break
	if count == 2:
		ans = sum(l) + 4
	elif count == 1:
		ans = sum(l)
	elif count == 0:
		ans = sum(l) - 4
	print(ans)


for i in range(int(input())):
	input()
	v = input()
	vv = sum(map(int, v.split()))
	if '-1 -1' in v:
		print(vv + 4)
	elif '-1 1' in v or '1 -1' in v:
		print(vv)
	elif '1 1' in v:
		print(vv - 4)


def flipFlop(a):
	suma = a[-1]
	pronaden = 0
	for i in range(len(a) - 1):
		if pronaden != 1:
			if a[i] == a[i + 1] == -1:
				pronaden = 1
			elif a[i] * a[i + 1] == -1:
				pronaden = 2
		suma += a[i]
	if pronaden == 1:
		return suma + 4
	elif pronaden == 2:
		return suma
	else:
		return suma - 4
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(flipFlop(a))


def solve():
	a = int(input())
	c = list(map(int, input().split()))
	cn = c.count(-1)
	if cn == 0:
		(c[0], c[1]) = (-1, -1)
		print(sum(c))
	else:
		for i in range(len(c) - 1):
			if c[i] == -1 and c[i + 1] == -1:
				(c[i], c[i + 1]) = (1, 1)
				break
		print(sum(c))
a = int(input())
for i in range(a):
	solve()


for z in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))[:n]
	s = sum(a)
	mi = 5
	for i in range(n - 1):
		if a[i] + a[i + 1] < mi:
			mi = a[i] + a[i + 1]
			if mi == -2:
				break
	if mi == 2:
		print(s - 4)
	elif mi == 0:
		print(s)
	else:
		print(s + 4)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 2:
		if a[0] == 1:
			a[0] = -1
		else:
			a[0] = 1
		if a[1] == -1:
			a[1] = 1
		else:
			a[1] = -1
	else:
		f = 0
		for i in range(n - 1):
			if a[i] == -1 and a[i + 1] == -1:
				f = 1
				break
		if f == 1:
			a[i] = 1
			a[i + 1] = 1
		else:
			f = 0
			for i in range(n - 1):
				if a[i] == 1 and a[i + 1] == -1 or (a[i] == -1 and a[i + 1] == 1):
					f = 1
					break
			if f == 1:
				a[i] = -a[i]
				a[i + 1] = -a[i + 1]
			else:
				a[0] = -a[0]
				a[1] = -a[1]
	print(sum(a))


for _ in range(int(input())):
	a = int(input())
	li = list(map(int, input().split()))
	count1 = sum(li)
	lo = count1
	for i in range(a - 1):
		if li[i] == -1 and li[i + 1] == -1:
			count1 = count1 + 4
			break
	if li.count(-1) == 1:
		print(lo)
	elif li.count(-1) == 0:
		print(lo - 4)
	else:
		print(count1)


t = int(input())
for i in range(t):
	l = int(input())
	k = list(map(int, input().split()))
	flag = 0
	res = sum(k)
	for i in range(l - 1):
		if k[i] == -1 and k[i + 1] == -1:
			flag = 1
			break
	if flag:
		res += 4
		print(res)
		continue
	for i in range(l - 1):
		if k[i] * k[i + 1] == -1:
			flag = 1
			break
	if flag:
		print(res)
	else:
		res -= 4
		print(res)


t = int(input())
for j in range(t):
	n = int(input())
	a = []
	f = 0
	a = list(map(int, input().split()))
	for i in range(len(a) - 1):
		if a[i] == -1 and a[i + 1] == -1:
			f = 1
			a[i] = 1
			a[i + 1] = 1
			break
	if f != 1:
		for i in range(len(a) - 1):
			if a[i] == -1 and a[i + 1] == 1 or (a[i] == 1 and a[i + 1] == -1):
				f = 2
				break
	if f == 0:
		for k in range(len(a) - 1):
			if a[k] == 1 and a[k + 1] == 1:
				a[k] = -1
				a[k + 1] = -1
			break
	print(sum(a))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	for j in range(n - 1):
		if l[j] == -1 and l[j + 1] == -1:
			l[j] = 1
			l[j + 1] = 1
			c = 1
			break
	if c == 0:
		for j in range(n - 1):
			if l[j] == -1 and l[j + 1] == 1 or (l[j] == 1 and l[j + 1] == -1):
				(l[j], l[j + 1]) = (l[j + 1], l[j])
				c = 1
				break
		if c == 0:
			for j in range(n - 1):
				if l[j] == 1 and l[j + 1] == 1:
					(l[j], l[j + 1]) = (-1, -1)
					c = 1
					break
	print(sum(l))


for _ in range(int(input())):
	n = int(input())
	elements = list(map(int, input().split()))
	(status, status2) = (False, False)
	if elements[n - 1] == -1:
		status2 = True
	for i in range(n - 2, -1, -1):
		if elements[i] == -1:
			status2 = True
		if elements[i] == -1 and elements[i + 1] == -1:
			elements[i] = 1
			elements[i + 1] = 1
			stauts = True
			break
	if status:
		print(sum(elements))
	elif status2:
		print(sum(elements))
	else:
		print(sum(elements) - 4)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	flag = False
	for i in range(n - 1):
		if arr[i] == arr[i + 1] == -1:
			flag = True
			break
	if flag:
		print(sum(arr) + 4)
	elif -1 in arr:
		print(sum(arr))
	else:
		print(sum(arr) - 4)


import sys

def main():
	t = int(input())
	for _ in range(t):
		n = input()
		n = list(map(int, input().split()))
		if -1 not in n:
			print(sum(n) - 4)
		elif '-1, -1' in str(n):
			print(sum(n) + 4)
		else:
			print(sum(n))
main()
sys.exit()


def max_sum(num_list, size):
	contain_negative = False
	for i in range(size - 1):
		if num_list[i] == -1 and num_list[i + 1] == -1:
			return sum(num_list) + 4
		elif num_list[i] == -1 or num_list[i + 1] == -1:
			contain_negative = True
	if contain_negative:
		return sum(num_list)
	return sum(num_list) - 4

def main():
	test_case_num = int(input())
	for _ in range(test_case_num):
		current_size = int(input())
		current_nums = input()
		current_list = current_nums.split()
		for i in range(current_size):
			current_list[i] = int(current_list[i])
		print(max_sum(current_list, current_size))
main()


for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	found = False
	for j in range(n - 1):
		if a[j] == -1 and a[j + 1] == -1:
			a[j] = 1
			a[j + 1] = 1
			found = True
			break
	if found == False and a.count(-1) == 0:
		print(sum(a) - 4)
	else:
		print(sum(a))


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if len(l) == 1:
		print(l[0])
	elif len(l) == 2:
		l1 = [i * -1 for i in l]
		print(sum(l1))
	elif len(l) > 2:
		x = l.count(-1)
		if x == 0:
			for i in range(0, len(l) - 1):
				if l[i] == l[i + 1]:
					l[i] = -1 * l[i]
					l[i + 1] = -1 * l[i + 1]
					break
			print(sum(l))
		if x > 0:
			for i in range(0, len(l) - 1):
				if l[i] == l[i + 1] == -1:
					l[i] = 1
					l[i + 1] = 1
					break
			print(sum(l))


def solve():
	n = int(input())
	spic = list(map(int, input().split()))
	tec = sum(spic)
	a = False
	for i in range(n - 1):
		if spic[i] == spic[i + 1] == -1:
			return tec + 4
		if spic[i] != spic[i + 1]:
			a = True
	if a:
		return tec
	return tec - 4
for i in range(int(input())):
	print(solve())


out = []
for _ in range(int(input())):
	n = int(input())
	s = input()
	a = [int(i) for i in s.split()]
	if '-1 -1' in s:
		out.append(sum(a) + 4)
	elif '-1' in s:
		out.append(sum(a))
	else:
		out.append(sum(a) - 4)
for i in out:
	print(i)


def helper(arr):
	ans = sum(arr)
	(pp, pm) = (False, False)
	for i in range(len(arr) - 1):
		if arr[i] == -1 and arr[i + 1] == -1:
			return ans + 4
		elif arr[i] == 1 and arr[i + 1] == 1:
			pp = True
		elif arr[i] == 1 and arr[i + 1] == -1 or (arr[i + 1] == 1 and arr[i] == -1):
			pm = True
	if pm:
		return ans
	elif pp:
		return ans - 4
for i in range(int(input())):
	n = int(input())
	print(helper(list(map(int, input().split()))))


for _ in range(int(input())):
	N = int(input())
	S = list(map(int, input().split()))
	for i in range(len(S) - 1):
		if S[i] == -1 and S[i + 1] == -1:
			print(sum(S) + 4)
			break
	else:
		if -1 in S:
			print(sum(S))
		else:
			print(sum(S) - 4)


import sys
import math
from bisect import bisect_right as br
from collections import deque, Counter
from itertools import combinations as cb
from collections import deque

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

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

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	arr = int_arr()
	sm = sum(arr)
	if -1 not in arr:
		print(sm - 4)
		continue
	for i in range(0, n - 1):
		if arr[i] == -1 and arr[i + 1] == -1:
			print(sm + 4)
			break
	else:
		print(sm)


try:
	for _ in range(int(input())):
		n = int(input())
		lst = list(map(int, input().split()))
		ans = 0
		flag1 = 0
		flag2 = 0
		for i in range(n - 1):
			if lst[i] == -1 and lst[i + 1] == -1:
				flag1 = 1
				break
			if lst[i] + lst[i + 1] == 0:
				flag2 = 1
		if flag1:
			print(sum(lst) + 4)
		elif flag2:
			print(sum(lst))
		else:
			print(sum(lst) - 4)
except Exception as e:
	print(e)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	res = False
	for i in range(n - 1):
		if l[i] == l[i + 1] == -1:
			l[i] = 1
			l[i + 1] = 1
			res = True
			break
	if res == False:
		for i in range(n - 1):
			if l[i] == 1 and l[i + 1] == -1:
				l[i] = -1
				l[i + 1] = 1
				res = True
				break
	if res == False:
		for i in range(n - 1):
			if l[i] == -1 and l[i + 1] == 1:
				l[i] = 1
				l[i + 1] = -1
				res = True
				break
	if res == False:
		for i in range(n - 1):
			if l[i] == 1 and l[i + 1] == 1:
				l[i] = -1
				l[i + 1] = -1
				break
	print(sum(l))


T = int(input())
for _ in range(0, T):
	n = int(input())
	s = str(input())
	if '-1 -1' in s:
		s = s.split()
		s = [int(i) for i in s]
		print(sum(s) + 4)
	elif '-1 1' in s or '1 -1' in s:
		s = s.split()
		s = [int(i) for i in s]
		print(sum(s))
	else:
		s = s.split()
		s = [int(i) for i in s]
		print(sum(s) - 4)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	k = 0
	for i in range(0, n - 1):
		if a[i] == -1 and a[i + 1] == -1:
			a[i] = 1
			a[i + 1] = 1
			k = 1
			break
		elif a[i] == 1 and a[i + 1] == -1 or (a[i] == -1 and a[i + 1] == 1):
			k = 2
	if k == 1 or k == 2:
		print(sum(a))
	else:
		print(sum(a) - 4)


t = int(input())
while t:
	n = int(input())
	a = [int(x) for x in input().split()]
	s = sum(a)
	if a.count(-1) == 0:
		print(s - 4)
		t -= 1
		continue
	elif a.count(1) == 0:
		print(s + 4)
		t -= 1
		continue
	for i in range(n - 1):
		if a[i] + a[i + 1] == -2:
			s += 4
			break
	print(s)
	t -= 1


t = int(input())
ans = []
for ti in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	s1 = sum(a)
	s1_max = s1 - 4
	for i in range(n - 1):
		p = a[i] * a[i + 1]
		if p < 0:
			s1_max = max(s1, s1_max)
		elif a[i] < 0:
			s1_max = s1 + 4
			break
	ans.append(s1_max)
for a in ans:
	print(a)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	flag = False
	for i in range(n - 1):
		if arr[i] < 0 and arr[i + 1] < 0:
			arr[i] = arr[i] * -1
			arr[i + 1] = arr[i + 1] * -1
			flag = True
			break
	if flag == False:
		for i in range(n - 1):
			if arr[i] == -1:
				arr[i] = 1
				arr[i + 1] = arr[i + 1] * -1
				flag = True
				break
	if flag == False:
		arr[-1] = arr[-1] * -1
		arr[-2] = arr[-2] * -1
	print(sum(arr))


for _ in range(int(input())):
	input()
	nums = list(map(int, input().split()))
	curr_sum = sum(nums)
	nn_exists = False
	np_exists = False
	for i in range(len(nums) - 1):
		if nums[i] == -1 and nums[i + 1] == -1:
			nn_exists = True
			break
		if nums[i] * nums[i + 1] == -1:
			np_exists = True
	if nn_exists:
		print(curr_sum + 4)
	elif np_exists:
		print(curr_sum)
	else:
		print(curr_sum - 4)


for i in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	c = 0
	z = 0
	for i in range(n - 1):
		if li[i] == -1 and li[i + 1] == -1:
			c = 4
			z = 1
			break
		if li[i] == -1 and li[i + 1] == 1:
			z = 2
			continue
		if li[i] == 1 and li[i + 1] == -1:
			z = 3
			continue
	if z == 0:
		print(sum(li) - 4)
		continue
	if z == 1:
		print(sum(li) + 4)
		continue
	if z == 2:
		print(sum(li))
		continue
	if z == 3:
		print(sum(li))
		continue


for _ in ' ' * int(input()):
	n = int(input())
	x = list(map(int, input().split()))
	s = sum(x)
	a = 0
	for i in range(n - 1):
		if x[i] + x[i + 1] == -2:
			print(s + 4)
			break
		if x[i] + x[i + 1] == 0:
			a = 1
	else:
		print(s - 4 * (a == 0))


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	k = 0
	for i in range(n - 1):
		if A[i] == -1 and A[i + 1] == -1:
			print(sum(A) + 4)
			k = 1
			break
	if k == 0:
		for i in range(n - 1):
			if A[i] == 1 and A[i + 1] == -1 or (A[i] == -1 and A[i + 1] == 1):
				print(sum(A))
				break
		else:
			print(sum(A) - 4)


n = int(input())
res = []
for i in range(n):
	k = int(input())
	mas = list(map(int, input().split()))
	for j in range(len(mas) - 1):
		if mas[j] == mas[j + 1] == -1:
			res.append(sum(mas) + 4)
			break
	else:
		if -1 in mas:
			res.append(sum(mas))
		else:
			res.append(sum(mas) - 4)
print(*res, sep='\n')


def exe():
	f = 0
	for i in lst:
		if i == -1:
			f = 1
	if f == 0:
		return n - 4
	for i in range(n - 1):
		if lst[i] == lst[i + 1] and lst[i] == -1:
			lst[i] = -1 * lst[i]
			lst[i + 1] = -1 * lst[i + 1]
			break
	s = 0
	for i in lst:
		s += i
	return s
for i in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	print(exe())


t = int(input())
for nouse in range(t):
	n = int(input())
	tmp = input()
	s = tmp.replace(' ', '')
	m = list(map(int, tmp.split()))
	if '-1-1' in s:
		print(m.count(1) - m.count(-1) + 4)
	elif '-11' in s or '1-1' in s:
		print(m.count(1) - m.count(-1))
	else:
		print(n - 4)


T = int(input())
for _ in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	track = -1
	end = False
	for i in range(n - 1):
		if arr[i] == -1 and arr[i + 1] == -1:
			arr[i] = -arr[i]
			arr[i + 1] = -arr[i + 1]
			print(sum(arr))
			end = True
			break
		if arr[i] == -1 and arr[i + 1] == 1 or (arr[i] == 1 and arr[i + 1] == -1):
			track = i
	if track != -1 and end == False:
		arr[track] = -arr[track]
		arr[track + 1] = -arr[track + 1]
		print(sum(arr))
	elif track == -1 and end == False:
		arr[0] = -arr[0]
		arr[1] = -arr[1]
		print(sum(arr))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = sum(a)
	set_point = a[0] + a[1]
	if set_point == -2:
		ans += 4
		print(ans)
	else:
		min_set_point = set_point
		i = 2
		while i < n:
			set_point += a[i] - a[i - 2]
			if set_point == -2:
				ans += 4
				break
			elif set_point < min_set_point:
				min_set_point = set_point
			i += 1
		if set_point == -2:
			print(ans)
		else:
			print(ans - 2 * min_set_point)


num = int(input())
for i in range(0, num):
	n = int(input())
	flag = 0
	l = list(map(int, input().split(' ')))
	if n == 2:
		l[0] = l[0] * -1
		l[1] = l[1] * -1
		print(l[0] + l[1])
		continue
	for i in range(0, n - 1):
		if l[i] == -1 and l[i + 1] == -1:
			flag = 1
			l[i] = 1
			l[i + 1] = 1
			break
	if flag == 0:
		if -1 in l:
			ind = l.index(-1)
			l[ind] = 1
			if ind != 0:
				l[0] = -1
			else:
				l[1] = -1
		else:
			l[0] = -1
			l[1] = -1
	print(sum(l))


t = int(input())
for l in range(t):
	n = int(input())
	num = list(map(int, input().split()))
	check = 0
	for i in range(n - 1):
		if num[i] == -1 and num[i + 1] == -1:
			check = 1
			break
	if check == 0:
		for j in range(n - 1):
			if num[j] == -1 and num[j + 1] == 1 or (num[j] == 1 and num[j + 1] == -1):
				check = 2
				break
	if check == 0:
		print(sum(num) - 4)
	elif check == 1:
		print(sum(num) + 4)
	elif check == 2:
		print(sum(num))