It's finally summer in Chefland! So our chef is looking forward to prepare some of the best "beat-the-heat" dishes to attract more customers. He summons the Wizard of Dessert to help him with one such dish.
The wizard provides the chef with a sequence of N ingredients where the i^{th} ingredient has a delish value of D[i]. The preparation of the dish takes place in two phases. 

Phase 1 : The chef chooses two indices i and j and adds the ingredients i, i+1, ..., j to his dish. He also finds the sum of the delish value in this range i.e D[i] + D[i+1] + ... + D[j].  

Phase 2 : The chef chooses two more indices k and l and adds the ingredients k, k+1, ..., l to his dish. He also finds the sum of the delish value in this range i.e D[k] + D[k+1] + ... + D[l]. 

Note that 1  ≤ i  ≤ j < k  ≤ l ≤ N. 

The total delish value of the dish is determined by the absolute difference between the values obtained in the two phases. Obviously, the chef wants to maximize the total delish value for his dish. So, he hires you to help him.
 
------ Input ------ 

First line of input contains an integer T denoting the number of test cases. For each test case, the first line contains an integer N denoting the number of ingredients. The next line contains N space separated integers where the i^{th} integer represents the delish value D[i] of the i^{th} ingredient.

------ Output ------ 

Print the maximum delish value of the dish that the chef can get.

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

$ 1 ≤ T ≤ 50 $
$ 2 ≤ N ≤ 10000 $
$ -1000000000 (−10^{9}) ≤ D[i] ≤ 1000000000 (10^{9}) 

----- Sample Input 1 ------ 
2
5
1 2 3 4 5
4
1 1 -1 -1
----- Sample Output 1 ------ 
13
4
----- explanation 1 ------ 
Example case 1.
Chef can choose i = j = 1, k = 2, l = 5.
The delish value hence obtained  is  | (2+3+4+5) ? (1) | = 13 .
 
Example case 2.
Chef can choose i = 1, j = 2, k = 3, l = 4.
The delish value hence obtained  is  | ( ( ?1 ) + ( ?1 ) ) ? ( 1 + 1 ) | = 4 .

Difficulty: MEDIUM_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
from math import inf

def left_max(n):
	max_fa = -inf
	max_end = 0
	for i in range(n - 1):
		max_end += arr[i]
		if max_end > max_fa:
			max_fa = max_end
		if max_end < 0:
			max_end = 0
		left_arr[i] = max_fa

def right_max(n):
	max_fa = -inf
	max_end = 0
	for i in range(n - 1, 0, -1):
		max_end += arr[i]
		if max_end > max_fa:
			max_fa = max_end
		if max_end < 0:
			max_end = 0
		right_arr[i - 1] = max_fa

def left_min(n):
	max_fa = -inf
	max_end = 0
	for i in range(n - 1):
		max_end += arr1[i]
		if max_end > max_fa:
			max_fa = max_end
		if max_end < 0:
			max_end = 0
		left_minarr[i] = -max_fa

def right_min(n):
	max_fa = -inf
	max_end = 0
	for i in range(n - 1, 0, -1):
		max_end += arr1[i]
		if max_end > max_fa:
			max_fa = max_end
		if max_end < 0:
			max_end = 0
		right_minarr[i - 1] = -max_fa
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr1 = [-arr[i] for i in range(len(arr))]
	left_arr = [0] * (n - 1)
	right_arr = [0] * (n - 1)
	left_minarr = [0] * (n - 1)
	right_minarr = [0] * (n - 1)
	left_max(n)
	right_max(n)
	left_min(n)
	right_min(n)
	ans = -1
	for i in range(len(left_arr)):
		ans = max(ans, abs(left_arr[i] - right_minarr[i]), abs(right_arr[i] - left_minarr[i]))
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	a = [[0, 0] for i in range(n)]
	b = [[0, 0] for i in range(n)]
	x = arr[0]
	y = arr[0]
	for i in range(1, n):
		a[i][0] = x
		a[i][1] = y
		if x < 0:
			x = arr[i]
		else:
			x += arr[i]
		if y > 0:
			y = arr[i]
		else:
			y += arr[i]
	x = 0
	y = 0
	for i in range(n - 1, -1, -1):
		if x < 0:
			x = arr[i]
		else:
			x += arr[i]
		if y > 0:
			y = arr[i]
		else:
			y += arr[i]
		b[i][0] = x
		b[i][1] = y
	ans = 0
	for i in range(1, n):
		c = abs(a[i][0] - b[i][1])
		d = abs(a[i][1] - b[i][0])
		c = max(c, d)
		ans = max(ans, c)
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	ar = [int(x) for x in input().split()]
	pos = [0] * n
	neg = [0] * n
	rpos = [0] * n
	rneg = [0] * n
	sm = 0
	ng = 0
	rsm = 0
	rng = 0
	pos[0] = ar[0]
	neg[n - 1] = ar[n - 1]
	rpos[n - 1] = ar[n - 1]
	rneg[0] = ar[0]
	for j in range(n):
		sm += ar[j]
		if sm <= 0:
			sm = 0
			if j > 0:
				pos[j] = ar[j]
		else:
			pos[j] = sm
		rng += ar[j]
		if rng >= 0:
			rng = 0
			if j > 0:
				rneg[j] = ar[j]
		else:
			rneg[j] = rng
	for j in range(n - 1, -1, -1):
		ng += ar[j]
		if ng >= 0:
			ng = 0
			if j < n - 1:
				neg[j] = ar[j]
		else:
			neg[j] = ng
		rsm += ar[j]
		if rsm <= 0:
			rsm = 0
			if j < n - 1:
				rpos[j] = ar[j]
		else:
			rpos[j] = rsm
	p = n - 1
	mx = 0
	mp = 0
	for j in range(1, n):
		pos[j] = max(pos[j - 1], pos[j])
		neg[p - j] = min(neg[p - j], neg[p - j + 1])
		rpos[p - j] = max(rpos[p - j], rpos[p - j + 1])
		rneg[j] = min(rneg[j - 1], rneg[j])
	for j in range(n - 1):
		mx = max(mx, abs(pos[j] - neg[j + 1]))
		mp = max(mp, abs(rneg[j] - rpos[j + 1]))
	print(max(mp, mx))
j


def fix_one(max1_e, min1_e, max1_s, min1_s):
	next_best = -10 ** 9 - 1
	for x in range(0, len(max1_e) - 1):
		next_best = max(abs(max1_e[x] - min1_s[x + 1]), abs(max1_s[x + 1] - min1_e[x]), next_best)
	return next_best
from sys import stdin
tc = int(stdin.readline())
for i in range(tc):
	n = int(stdin.readline())
	list1 = list(map(int, stdin.readline().split()))
	max1_e = [0] * n
	min1_e = [0] * n
	max_e = [0] * n
	min_e = [0] * n
	max1_e[0] = min1_e[0] = max_e[0] = max_until_now = min_e[0] = min_until_now = list1[0]
	for j in range(1, n):
		max1_e[j] = max(list1[j], max1_e[j - 1] + list1[j])
		if max1_e[j] > max_until_now:
			max_until_now = max1_e[j]
		max_e[j] = max_until_now
		min1_e[j] = min(list1[j], min1_e[j - 1] + list1[j])
		if min1_e[j] < min_until_now:
			min_until_now = min1_e[j]
		min_e[j] = min_until_now
	max1_s = [0] * n
	min1_s = [0] * n
	max_s = [0] * n
	min_s = [0] * n
	max1_s[n - 1] = min1_s[n - 1] = max_s[n - 1] = max_until_now = min_s[n - 1] = min_until_now = list1[n - 1]
	for k in range(n - 2, -1, -1):
		max1_s[k] = max(list1[k], max1_s[k + 1] + list1[k])
		if max1_s[k] > max_until_now:
			max_until_now = max1_s[k]
		max_s[k] = max_until_now
		min1_s[k] = min(list1[k], min1_s[k + 1] + list1[k])
		if min1_s[k] < min_until_now:
			min_until_now = min1_s[k]
		min_s[k] = min_until_now
	print(fix_one(max_e, min_e, max_s, min_s))


t = int(input())
while t != 0:
	n = int(input())
	a = list(map(int, input().split()))
	max_left = a[:]
	min_left = a[:]
	min_right = a[:]
	max_right = a[:]
	max_diff = 0
	for i in range(1, n):
		max_left[i] = max(max_left[i - 1] + a[i], a[i])
		min_left[i] = min(min_left[i - 1] + a[i], a[i])
	for i in range(n - 2, -1, -1):
		max_right[i] = max(max_right[i + 1] + a[i], a[i])
		min_right[i] = min(min_right[i + 1] + a[i], a[i])
	for i in range(n - 1):
		max_diff = max(max_diff, abs(min_left[i] - max_right[i + 1]))
		max_diff = max(max_diff, abs(max_left[i] - min_right[i + 1]))
	print(max_diff)
	t -= 1


def maxSubArray(nums):
	n = len(nums)
	dp = [float('-inf')] * n
	for i in range(n):
		dp[i] = max((dp[i - 1] if i > 0 else 0) + nums[i], nums[i])
	return dp

def minSubArray(nums):
	n = len(nums)
	dp = [float('inf')] * n
	for i in range(n):
		dp[i] = min((dp[i - 1] if i > 0 else 0) + nums[i], nums[i])
	return dp

def solve(arr):
	n = len(arr)
	max_from_left = maxSubArray(arr)
	max_from_right = maxSubArray(arr[::-1])[::-1]
	min_from_left = minSubArray(arr)
	min_from_right = minSubArray(arr[::-1])[::-1]
	max_diff = float('-inf')
	for split in range(n - 1):
		max_diff = max(max_diff, max_from_left[split] - min_from_right[split + 1])
		max_diff = max(max_diff, max_from_right[split + 1] - min_from_left[split])
	return max_diff
for T in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	print(solve(arr))


def solve(a, n):
	prefix_max = [0] * n
	prefix_min = [0] * n
	suffix_max = [0] * n
	suffix_min = [0] * n
	for i in range(n):
		if i == 0:
			prefix_max[i] = a[i]
			prefix_min[i] = a[i]
			suffix_max[n - i - 1] = a[n - i - 1]
			suffix_min[n - i - 1] = a[n - i - 1]
		else:
			prefix_max[i] = max(prefix_max[i - 1], 0) + a[i]
			prefix_min[i] = min(prefix_min[i - 1], 0) + a[i]
			suffix_max[n - i - 1] = max(suffix_max[n - i], 0) + a[n - i - 1]
			suffix_min[n - i - 1] = min(suffix_min[n - i], 0) + a[n - i - 1]
	ans = 0
	for i in range(n - 1):
		ans = max(ans, max(abs(prefix_max[i] - suffix_min[i + 1]), abs(prefix_min[i] - suffix_max[i + 1])))
	return ans
for _ in range(int(input())):
	n = int(input())
	a = tuple(map(int, input().split()))
	result = solve(a, n)
	print(result)


def lrimax(n, l):
	dplri = [0] * n
	dplri[0] = l[0]
	for i in range(1, n):
		dplri[i] = max(dplri[i - 1] + l[i], l[i])
	for i in range(1, n):
		dplri[i] = max(dplri[i - 1], dplri[i])
	return dplri

def lrimin(n, l):
	dp = [999999999999999999999999999] * n
	dp[0] = l[0]
	for i in range(1, n):
		dp[i] = min(l[i], l[i] + dp[i - 1])
	for i in range(1, n):
		dp[i] = min(dp[i - 1], dp[i])
	return dp

def rlimax(n, l):
	dp = [0] * n
	dp[n - 1] = l[n - 1]
	for i in range(n - 2, -1, -1):
		dp[i] = max(dp[i + 1] + l[i], l[i])
	for i in range(n - 2, -1, -1):
		dp[i] = max(dp[i], dp[i + 1])
	return dp

def rlimin(n, l):
	dp = [9999999999999999999999999999] * n
	dp[n - 1] = l[n - 1]
	for i in range(n - 2, -1, -1):
		dp[i] = min(dp[i + 1] + l[i], l[i])
	for i in range(n - 2, -1, -1):
		dp[i] = min(dp[i], dp[i + 1])
	return dp
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	lrmax = lrimax(n, l)
	rlmin = rlimin(n, l)
	lrmin = lrimin(n, l)
	rlmax = rlimax(n, l)
	maxi = -9999999999999999999999999999999999999999
	for i in range(n - 1):
		maxi = max(abs(lrmax[i] - rlmin[i + 1]), abs(rlmax[i + 1] - lrmin[i]), maxi)
	print(maxi)


for _ in range(int(input())):
	n = int(input())
	my = [int(i) for i in input().split()]
	leftmax = [my[0]]
	rightmax = [1000000]
	rightmin = [1000000]
	leftmin = [my[0]]
	total = my[0]
	totmin = my[0]
	for i in range(1, n):
		leftmax.append(0)
		rightmax.append(0)
		leftmin.append(1000000)
		rightmin.append(1000000)
	for i in range(1, len(my)):
		leftmax[i] = max(total + my[i], max(my[i], leftmax[i - 1]))
		leftmin[i] = min(totmin + my[i], min(my[i], leftmin[i - 1]))
		total = max(my[i], total + my[i])
		totmin = min(my[i], totmin + my[i])
	total = my[n - 1]
	totmin = my[n - 1]
	rightmin[n - 1] = my[n - 1]
	rightmax[n - 1] = my[n - 1]
	for i in range(n - 2, -1, -1):
		rightmax[i] = max(total + my[i], max(my[i], rightmax[i + 1]))
		rightmin[i] = min(totmin + my[i], min(my[i], rightmin[i + 1]))
		total = max(my[i], total + my[i])
		totmin = min(my[i], totmin + my[i])
	ans = 0
	for i in range(1, n):
		ans = max(leftmax[i - 1] - rightmin[i], max(rightmax[i] - leftmin[i - 1], ans))
	print(ans)


T = int(input())
ans = []
for _ in range(T):
	N = int(input())
	D = [int(i) for i in input().split()]
	lmax = [D[0]] * N
	lmin = [D[0]] * N
	rmax = [D[-1]] * N
	rmin = [D[-1]] * N
	for i in range(1, N):
		lmin[i] = min(lmin[i - 1] + D[i], D[i])
		lmax[i] = max(lmax[i - 1] + D[i], D[i])
	for i in range(N - 2, -1, -1):
		rmin[i] = min(rmin[i + 1] + D[i], D[i])
		rmax[i] = max(rmax[i + 1] + D[i], D[i])
	s = 0
	for i in range(N - 1):
		s = max(lmax[i] - rmin[i + 1], rmax[i + 1] - lmin[i], s)
	ans.append(s)
for i in ans:
	print(i)


t = int(input())
for x in range(t):
	n = int(input())
	m = input().strip().split()
	a = []
	for val in m:
		a.append(int(val))
	f = list()
	b = list()
	for i in range(n):
		f.append([0, 0])
		b.append([0, 0])
	f[0][0] = a[0]
	f[0][1] = a[0]
	for i in range(1, n):
		m1 = max(f[i - 1][0], 0) + a[i]
		m2 = min(f[i - 1][1], 0) + a[i]
		f[i][0] = m1
		f[i][1] = m2
	b[n - 1][0] = a[n - 1]
	b[n - 1][1] = a[n - 1]
	for i in range(n - 2, -1, -1):
		b1 = max(b[i + 1][0], 0) + a[i]
		b2 = min(b[i + 1][1], 0) + a[i]
		b[i][0] = b1
		b[i][1] = b2
	ans = float('-inf')
	for i in range(0, n - 1):
		ans = max(ans, abs(f[i][0] - b[i + 1][1]))
		ans = max(ans, abs(f[i][1] - b[i + 1][0]))
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	minleft = [0] * n
	maxleft = [0] * n
	minright = [0] * n
	maxright = [0] * n
	minleft[0] = maxleft[0] = a[0]
	for i in range(1, n):
		minleft[i] = min(minleft[i - 1] + a[i], a[i])
		maxleft[i] = max(maxleft[i - 1] + a[i], a[i])
	minright[n - 1] = a[n - 1]
	maxright[n - 1] = a[n - 1]
	for i in range(n - 2, -1, -1):
		minright[i] = min(minright[i + 1] + a[i], a[i])
		maxright[i] = max(maxright[i + 1] + a[i], a[i])
	max_diff = 0
	for i in range(n - 1):
		max_diff = max(max_diff, abs(minleft[i] - maxright[i + 1]))
		max_diff = max(max_diff, abs(minleft[i] - minright[i + 1]))
		max_diff = max(max_diff, abs(maxleft[i] - maxright[i + 1]))
		max_diff = max(max_diff, abs(maxleft[i] - minright[i + 1]))
	print(max_diff)


T = int(input())
for i in range(T):
	n = int(input())
	l = list(map(int, input().split()))
	premin = [0] * n
	premax = [0] * n
	sufmin = [0] * n
	sufmax = [0] * n
	premin[0] = premax[0] = l[0]
	sufmin[-1] = sufmax[-1] = l[-1]
	for i in range(1, n):
		premin[i] = min(premin[i - 1], 0) + l[i]
		premax[i] = max(premax[i - 1], 0) + l[i]
	for i in range(n - 2, -1, -1):
		sufmin[i] = min(sufmin[i + 1], 0) + l[i]
		sufmax[i] = max(sufmax[i + 1], 0) + l[i]
	ans = 0
	for i in range(n - 1):
		ans = max(ans, abs(premax[i] - sufmin[i + 1]))
		ans = max(ans, abs(premin[i] - sufmax[i + 1]))
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	(lmax, lmin, rmax, rmin) = ([0] * n, [0] * n, [0] * n, [0] * n)
	lmax[0] = l[0]
	lmin[0] = l[0]
	rmax[-1] = l[-1]
	rmin[-1] = l[-1]
	for i in range(1, len(l)):
		lmax[i] = max(lmax[i - 1] + l[i], l[i])
		lmin[i] = min(lmin[i - 1] + l[i], l[i])
	for i in range(n - 2, -1, -1):
		rmax[i] = max(rmax[i + 1] + l[i], l[i])
		rmin[i] = min(rmin[i + 1] + l[i], l[i])
	ans = 0
	for i in range(n - 1):
		ans = max(ans, max(abs(rmax[i + 1] - lmin[i]), abs(rmin[i + 1] - lmax[i])))
	print(ans)


for case in range(int(input())):
	N = int(input())
	L = list(map(int, input().split()))
	leftMaSum = [None] * N
	leftMiSum = [None] * N
	leftMa = [None] * N
	leftMi = [None] * N
	leftMaSum[0] = L[0]
	leftMiSum[0] = L[0]
	leftMa[0] = L[0]
	leftMi[0] = L[0]
	for i in range(1, N):
		num = L[i]
		leftMaSum[i] = max(num + leftMaSum[i - 1], num)
		leftMiSum[i] = min(num + leftMiSum[i - 1], num)
		leftMa[i] = max(leftMaSum[i], leftMa[i - 1])
		leftMi[i] = min(leftMiSum[i], leftMi[i - 1])
	rightMaSum = [None] * N
	rightMiSum = [None] * N
	rightMa = [None] * N
	rightMi = [None] * N
	rightMaSum[-1] = L[-1]
	rightMiSum[-1] = L[-1]
	rightMa[-1] = L[-1]
	rightMi[-1] = L[-1]
	for i in range(N - 2, -1, -1):
		num = L[i]
		rightMaSum[i] = max(num + rightMaSum[i + 1], num)
		rightMiSum[i] = min(num + rightMiSum[i + 1], num)
		rightMa[i] = max(rightMaSum[i], rightMa[i + 1])
		rightMi[i] = min(rightMiSum[i], rightMi[i + 1])
	v1 = abs(leftMa[0] - rightMa[1])
	v2 = abs(leftMa[0] - rightMi[1])
	v3 = abs(leftMi[0] - rightMa[1])
	v4 = abs(leftMi[0] - rightMi[1])
	ans = max(v1, v2, v3, v4)
	for i in range(1, N - 1):
		v1 = abs(leftMa[i] - rightMa[i + 1])
		v2 = abs(leftMa[i] - rightMi[i + 1])
		v3 = abs(leftMi[i] - rightMa[i + 1])
		v4 = abs(leftMi[i] - rightMi[i + 1])
		ans = max(ans, v1, v2, v3, v4)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	dp1 = [0] * n
	dp2 = [0] * n
	dp3 = [0] * n
	dp4 = [0] * n
	cs = a[0]
	gs = a[0]
	dp1[0] = cs
	for i in range(1, n):
		cs = max(a[i], cs + a[i])
		gs = max(cs, gs)
		dp1[i] = gs
	cs = gs = a[-1]
	dp2[-1] = cs
	for i in range(n - 2, -1, -1):
		cs = max(a[i], cs + a[i])
		gs = max(cs, gs)
		dp2[i] = gs
	cs = gs = a[0]
	dp3[0] = cs
	for i in range(1, n):
		cs = min(a[i], cs + a[i])
		gs = min(cs, gs)
		dp3[i] = gs
	cs = gs = a[-1]
	dp4[-1] = cs
	for i in range(n - 2, -1, -1):
		cs = min(a[i], cs + a[i])
		gs = min(cs, gs)
		dp4[i] = gs
	mx = 0
	for i in range(n - 1):
		mx = max(mx, abs(dp1[i] - dp4[i + 1]), abs(dp2[i + 1] - dp3[i]))
	print(mx)


t = int(input())
for _ in range(t):
	n = int(input())
	li = list(map(int, input().split()))
	(rmax, rmin, lmax, lmin) = ([0] * n, [0] * n, [0] * n, [0] * n)
	(rmax[-1], rmin[-1], lmax[0], lmin[0]) = (li[-1], li[-1], li[0], li[0])
	for i in range(n - 2, -1, -1):
		rmax[i] = max(rmax[i + 1] + li[i], li[i])
		rmin[i] = min(rmin[i + 1] + li[i], li[i])
	for i in range(1, n):
		lmax[i] = max(lmax[i - 1] + li[i], li[i])
		lmin[i] = min(lmin[i - 1] + li[i], li[i])
	result = []
	for i in range(n - 1):
		result.append(abs(lmax[i] - rmin[i + 1]))
		result.append(abs(lmin[i] - rmax[i + 1]))
	print(max(result))


import sys
for t in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	lma = [0 for i in range(n)]
	lmi = [0 for i in range(n)]
	rma = [0 for i in range(n)]
	rmi = [0 for i in range(n)]
	s1 = a[0]
	s2 = a[-1]
	ma = ma1 = -sys.maxsize
	mi = mi1 = sys.maxsize
	s = 0
	o = 0
	s1 = 0
	o1 = 0
	for i in range(0, n - 1):
		j = n - i - 1
		s += a[i]
		o += a[i]
		s1 += a[j]
		o1 += a[j]
		ma = max(ma, s)
		mi = min(mi, o)
		ma1 = max(ma1, s1)
		mi1 = min(mi1, o1)
		if s < 0:
			s = 0
		if o > 0:
			o = 0
		if s1 < 0:
			s1 = 0
		if o1 > 0:
			o1 = 0
		lmi[i] = mi
		lma[i] = ma
		rmi[j] = mi1
		rma[j] = ma1
	ans = max(abs(lmi[0] - rma[1]), abs(lma[0] - rmi[1]))
	for i in range(n - 1):
		y = max(abs(lmi[i] - rma[i + 1]), abs(lma[i] - rmi[i + 1]))
		ans = ans if ans > y else y
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	d = list(map(int, input().split()))
	(o1, o2, r1, r2) = ([], [], [], [])
	(m1, m2, p1, p2) = (d[0], d[0], d[-1], d[-1])
	(l1, l2, l3, l4) = (0, 0, 0, 0)
	for j in range(n):
		l1 += d[j]
		l2 += d[j]
		l3 += d[-j - 1]
		l4 += d[-j - 1]
		if l1 > m1:
			m1 = l1
		if l2 < m2:
			m2 = l2
		if l3 > p1:
			p1 = l3
		if l4 < p2:
			p2 = l4
		o1.append(m1)
		o2.append(m2)
		r1.append(p1)
		r2.append(p2)
		if l1 < 0:
			l1 = 0
		if l2 > 0:
			l2 = 0
		if l3 < 0:
			l3 = 0
		if l4 > 0:
			l4 = 0
	c = 0
	for k in range(n - 1):
		c = max(abs(o1[k] - r2[n - 2 - k]), abs(o2[k] - r1[n - 2 - k]), c)
	print(c)


for _ in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	(HardLeftMin, HardLeftMax, SoftLeftMax, SoftLeftMin, HardRightMax, HardRightMin) = ([0] * N, [0] * N, [0] * N, [0] * N, [0] * N, [0] * N)
	for i in range(N):
		HardLeftMin[i] = min((HardLeftMin[i - 1] if i - 1 >= 0 else 0) + arr[i], arr[i])
		HardLeftMax[i] = max((HardLeftMax[i - 1] if i - 1 >= 0 else 0) + arr[i], arr[i])
		SoftLeftMax[i] = max(HardLeftMax[i], SoftLeftMax[i - 1] if i - 1 >= 0 else HardLeftMax[i])
		SoftLeftMin[i] = min(HardLeftMin[i], SoftLeftMin[i - 1] if i - 1 >= 0 else HardLeftMin[i])
	for i in range(N - 1, -1, -1):
		HardRightMin[i] = min((HardRightMin[i + 1] if i + 1 < N else 0) + arr[i], arr[i])
		HardRightMax[i] = max((HardRightMax[i + 1] if i + 1 < N else 0) + arr[i], arr[i])
	ans = 0
	for i in range(N):
		if i != N - 1:
			ans = max(ans, SoftLeftMax[i] - HardRightMin[i + 1])
		if i != 0:
			ans = max(ans, HardRightMax[i] - SoftLeftMin[i - 1])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	min_left = [0] * n
	max_left = [0] * n
	min_right = [0] * n
	max_right = [0] * n
	min_left[0] = max_left[0] = l[0]
	min_right[n - 1] = max_right[n - 1] = l[n - 1]
	for i in range(1, n):
		min_left[i] = min(l[i], l[i] + min_left[i - 1])
		max_left[i] = max(l[i], l[i] + max_left[i - 1])
	for i in range(n - 2, -1, -1):
		min_right[i] = min(l[i], l[i] + min_right[i + 1])
		max_right[i] = max(l[i], l[i] + max_right[i + 1])
	ans = 0
	for i in range(n - 1):
		ans = max(ans, abs(min_left[i] - max_right[i + 1]))
		ans = max(ans, abs(max_left[i] - min_right[i + 1]))
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	i = [0] * n
	i[0] = a[0]
	j = [0] * n
	j[0] = a[0]
	k = [0] * n
	k[-1] = a[-1]
	l = [0] * n
	l[-1] = a[-1]
	for x in range(1, n):
		i[x] = min(i[x - 1] + a[x], a[x])
		j[x] = max(j[x - 1] + a[x], a[x])
		k[-1 - x] = min(k[-x] + a[-1 - x], a[-1 - x])
		l[-1 - x] = max(l[-x] + a[-1 - x], a[-1 - x])
	ans = max(j[0] - k[1], l[-1] - i[-2])
	for x in range(1, n - 1):
		ans = max(ans, j[x] - k[x + 1], l[x] - i[x - 1])
	print(ans)


def solve(arr, n):
	ans = -10 ** 20
	dp = [0] * n
	dp[0] = arr[0]
	dp2 = [10 ** 20] * n
	dp2[n - 1] = arr[n - 1]
	for i in range(1, n):
		dp[i] = max(arr[i], dp[i - 1] + arr[i])
	for i in range(n - 2, -1, -1):
		dp2[i] = min(arr[i], dp2[i + 1] + arr[i])
	maxpref = [0] * n
	minsuff = [0] * n
	maxpref[0] = dp[0]
	minsuff[n - 1] = dp2[n - 1]
	for i in range(1, n):
		maxpref[i] = max(maxpref[i - 1], dp[i])
	for i in range(n - 2, -1, -1):
		minsuff[i] = min(minsuff[i + 1], dp2[i])
	for i in range(n - 1):
		ans = max(ans, abs(maxpref[i] - minsuff[i + 1]))
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(j) for j in input().split()]
	print(max(solve(arr, n), solve(arr[::-1], n)))


n = int(input())
for _ in range(n):
	total = int(input())
	arr = list(map(int, input().split()))
	rightmax = [0] * total
	leftmax = [0] * total
	rightmin = [0] * total
	leftmin = [0] * total
	rightmax[0] = arr[0]
	leftmax[-1] = arr[-1]
	rightmin[0] = arr[0]
	leftmin[-1] = arr[-1]
	for i in range(1, total):
		rightmax[i] = max(arr[i], rightmax[i - 1] + arr[i])
		rightmin[i] = min(arr[i], rightmin[i - 1] + arr[i])
	for i in range(total - 2, -1, -1):
		leftmax[i] = max(arr[i], leftmax[i + 1] + arr[i])
		leftmin[i] = min(arr[i], leftmin[i + 1] + arr[i])
	max1 = float('-inf')
	i = 0
	while i + 1 < total:
		diff = abs(rightmax[i] - leftmin[i + 1])
		diff1 = abs(leftmax[i + 1] - rightmin[i])
		max1 = max(max1, diff, diff1)
		i += 1
	print(max1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	min_p = [a[0]] * n
	max_p = [a[0]] * n
	for i in range(1, n):
		min_p[i] = min(min_p[i - 1] + a[i], a[i])
		max_p[i] = max(max_p[i - 1] + a[i], a[i])
	min_s = [a[-1]] * n
	max_s = [a[-1]] * n
	for i in range(n - 2, -1, -1):
		min_s[i] = min(min_s[i + 1] + a[i], a[i])
		max_s[i] = max(max_s[i + 1] + a[i], a[i])
	ans = 0
	for i in range(n - 1):
		ans = max(ans, max_s[i + 1] - min_p[i], max_p[i] - min_s[i + 1])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	leftdp = [[0 for i in range(n)] for j in range(2)]
	rightdp = [[0 for i in range(n)] for j in range(2)]
	leftdp[0][0] = a[0]
	leftdp[1][0] = a[0]
	for i in range(1, n):
		leftdp[0][i] = max(leftdp[0][i - 1], 0) + a[i]
		leftdp[1][i] = min(leftdp[1][i - 1], 0) + a[i]
	rightdp[0][n - 1] = a[n - 1]
	rightdp[1][n - 1] = a[n - 1]
	for i in range(n - 2, -1, -1):
		rightdp[0][i] = max(rightdp[0][i + 1], 0) + a[i]
		rightdp[1][i] = min(rightdp[1][i + 1], 0) + a[i]
	ans = 0
	for i in range(n - 1):
		ans = max(ans, abs(leftdp[0][i] - rightdp[1][i + 1]))
		ans = max(ans, abs(leftdp[1][i] - rightdp[0][i + 1]))
	print(ans)


for t in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	(rmx, rmn, lmx, lmn) = ([0] * n, [0] * n, [0] * n, [0] * n)
	(rmx[-1], rmn[-1], lmx[0], lmn[0]) = (li[-1], li[-1], li[0], li[0])
	for i in range(n - 2, -1, -1):
		rmx[i] = max(rmx[i + 1] + li[i], li[i])
		rmn[i] = min(rmn[i + 1] + li[i], li[i])
	for i in range(1, n):
		lmx[i] = max(lmx[i - 1] + li[i], li[i])
		lmn[i] = min(lmn[i - 1] + li[i], li[i])
	res = []
	for i in range(n - 1):
		res.append(abs(lmx[i] - rmn[i + 1]))
		res.append(abs(lmn[i] - rmx[i + 1]))
	print(max(res))


T = int(input())
import numpy as np

def max_sub_min(arr):
	N = len(arr)
	max_till_i = np.zeros(N)
	min_from_i = np.zeros(N)
	best_max_till_i = np.zeros(N)
	best_min_from_i = np.zeros(N)
	best_max = arr[0]
	best_min = arr[-1]
	for i in range(N):
		if i == 0:
			max_till_i[i] = arr[i]
			min_from_i[-i - 1] = arr[-i - 1]
		else:
			max_till_i[i] = arr[i] + max(0, max_till_i[i - 1])
			min_from_i[-i - 1] = arr[-i - 1] + min(0, min_from_i[-i])
		best_max = max(best_max, max_till_i[i])
		best_min = min(best_min, min_from_i[-i - 1])
		best_max_till_i[i] = best_max
		best_min_from_i[-i - 1] = best_min
	best_diff = 0
	for i in range(N - 1):
		if best_max_till_i[i] - best_min_from_i[i + 1] > best_diff:
			best_diff = best_max_till_i[i] - best_min_from_i[i + 1]
	return int(best_diff)
for i in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	print(max(max_sub_min(arr), max_sub_min(arr[::-1])))


def findMax(x):
	c = x[0]
	for i in range(1, len(x)):
		if c < 0:
			c = 0
		c += x[i]
		if c < x[i - 1]:
			x[i] = x[i - 1]
		else:
			x[i] = c
for _ in range(int(input())):
	N = int(input())
	d = list(map(int, input().split()))
	min1 = d.copy()
	min2 = d.copy()
	min2.reverse()
	for i in range(N):
		min1[i] = -min1[i]
		min2[i] = -min2[i]
	max1 = d.copy()
	max2 = d.copy()
	max2.reverse()
	findMax(min1)
	findMax(min2)
	findMax(max1)
	findMax(max2)
	ans = 0
	for i in range(N - 1):
		d1 = -min1[i] - max2[N - i - 2]
		if d1 < 0:
			d1 = -d1
		if ans < d1:
			ans = d1
		d1 = max1[i] + min2[N - i - 2]
		if d1 < 0:
			d1 = -d1
		if ans < d1:
			ans = d1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	delish = list(map(int, input().split()))
	(r_max, r_min) = ([0] * n, [0] * n)
	(l_max, l_min) = ([0] * n, [0] * n)
	(all_max, all_min, cur_max, cur_min) = (-10000000000, 10000000000, 0, 10000000000)
	(all_maxb, all_minb, cur_maxb, cur_minb) = (-10000000000, 10000000000, 0, 10000000000)
	for i in range(n):
		cur_max += delish[i]
		all_max = max(all_max, cur_max)
		if cur_max < 0:
			cur_max = 0
		r_max[i] = all_max
		if cur_min > 0:
			cur_min = delish[i]
		else:
			cur_min += delish[i]
		all_min = min(cur_min, all_min)
		r_min[i] = all_min
		cur_maxb += delish[n - i - 1]
		all_maxb = max(all_maxb, cur_maxb)
		if cur_maxb < 0:
			cur_maxb = 0
		l_max[n - i - 1] = all_maxb
		if cur_minb > 0:
			cur_minb = delish[n - i - 1]
		else:
			cur_minb += delish[n - i - 1]
		all_minb = min(cur_minb, all_minb)
		l_min[n - i - 1] = all_minb
	print(max((max(abs(r_max[j] - l_min[j + 1]), abs(r_min[j] - l_max[j + 1])) for j in range(n - 1))))


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	startmax = [0] * n
	startmin = [0] * n
	endmax = [0] * n
	endmin = [0] * n
	(startmax[n - 1], startmin[n - 1]) = (A[n - 1], A[n - 1])
	(endmax[0], endmin[0]) = (A[0], A[0])
	for i in range(n - 2, -1, -1):
		startmax[i] = max(startmax[i + 1] + A[i], A[i])
		startmin[i] = min(startmin[i + 1] + A[i], A[i])
		j = n - 1 - i
		endmax[j] = max(endmax[j - 1] + A[j], A[j])
		endmin[j] = min(endmin[j - 1] + A[j], A[j])
	for i in range(n - 2, -1, -1):
		startmax[i] = max(startmax[i + 1], startmax[i])
		startmin[i] = min(startmin[i + 1], startmin[i])
		j = n - 1 - i
		endmax[j] = max(endmax[j - 1], endmax[j])
		endmin[j] = min(endmin[j - 1], endmin[j])
	ans = -1
	for i in range(n - 1):
		ans = max(abs(startmax[i + 1] - endmin[i]), abs(startmin[i + 1] - endmax[i]), ans)
	print(ans)


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	a = [int(i) for i in sys.stdin.readline().split()]
	min_p = [a[0]] * n
	max_p = [a[0]] * n
	for i in range(1, n):
		min_p[i] = min(min_p[i - 1] + a[i], a[i])
		max_p[i] = max(max_p[i - 1] + a[i], a[i])
	min_s = [a[-1]] * n
	max_s = [a[-1]] * n
	for i in range(n - 2, -1, -1):
		min_s[i] = min(min_s[i + 1] + a[i], a[i])
		max_s[i] = max(max_s[i + 1] + a[i], a[i])
	ans = 0
	for i in range(n - 1):
		ans = max(ans, max_p[i] - min_s[i + 1], max_s[i + 1] - min_p[i])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	minleft = n * [0]
	maxleft = n * [0]
	minleft[0] = maxleft[0] = ar[0]
	for i in range(1, n):
		minleft[i] = min(ar[i], minleft[i - 1] + ar[i])
		maxleft[i] = max(ar[i], maxleft[i - 1] + ar[i])
	minright = n * [0]
	maxright = n * [0]
	minright[n - 1] = maxright[n - 1] = ar[n - 1]
	for i in range(n - 2, -1, -1):
		minright[i] = min(ar[i], minright[i + 1] + ar[i])
		maxright[i] = max(ar[i], maxright[i + 1] + ar[i])
	maxdiff = 0
	for i in range(n - 1):
		maxdiff = max(maxdiff, abs(minleft[i] - maxright[i + 1]))
		maxdiff = max(maxdiff, abs(maxleft[i] - minright[i + 1]))
	print(maxdiff)


import sys
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	lmax = [0 for i in range(n)]
	lmin = [0 for i in range(n)]
	rmax = [0 for i in range(n)]
	rmin = [0 for i in range(n)]
	(c1, c2) = (l[0], l[0])
	(m1, m2) = (l[0], l[0])
	(lmax[0], lmin[0]) = (l[0], l[0])
	(rmax[-1], rmin[-1]) = (l[-1], l[-1])
	for i in range(1, n):
		c1 += l[i]
		c2 += l[i]
		c1 = max(c1, l[i])
		c2 = min(c2, l[i])
		m1 = max(m1, c1)
		m2 = min(m2, c2)
		lmax[i] = m1
		lmin[i] = m2
	(c1, c2) = (l[-1], l[-1])
	(m1, m2) = (l[-1], l[-1])
	for i in range(n - 2, -1, -1):
		c1 += l[i]
		c2 += l[i]
		c1 = max(c1, l[i])
		c2 = min(c2, l[i])
		m1 = max(m1, c1)
		m2 = min(m2, c2)
		rmax[i] = m1
		rmin[i] = m2
	m = -sys.maxsize
	for i in range(1, n):
		m = max(m, abs(rmax[i] - lmin[i - 1]), abs(rmin[i] - lmax[i - 1]))
	print(m)


T = int(input())
for tc in range(T):
	N = int(input())
	D = list(map(int, input().split()))
	Omaxlist = []
	Ominlist = []
	Rmaxlist = []
	Rminlist = []
	Omax = D[0]
	Omin = D[0]
	Rmax = D[-1]
	Rmin = D[-1]
	Olocalmax = 0
	Olocalmin = 0
	Rlocalmax = 0
	Rlocalmin = 0
	for i in range(N):
		Olocalmax += D[i]
		Olocalmin += D[i]
		Rlocalmax += D[-i - 1]
		Rlocalmin += D[-i - 1]
		if Olocalmax > Omax:
			Omax = Olocalmax
		if Olocalmin < Omin:
			Omin = Olocalmin
		if Rlocalmax > Rmax:
			Rmax = Rlocalmax
		if Rlocalmin < Rmin:
			Rmin = Rlocalmin
		Omaxlist.append(Omax)
		Ominlist.append(Omin)
		Rmaxlist.append(Rmax)
		Rminlist.append(Rmin)
		if Olocalmax < 0:
			Olocalmax = 0
		if Olocalmin > 0:
			Olocalmin = 0
		if Rlocalmax < 0:
			Rlocalmax = 0
		if Rlocalmin > 0:
			Rlocalmin = 0
	dif = 0
	for j in range(N - 1):
		dif = max(abs(Omaxlist[j] - Rminlist[N - 2 - j]), abs(Ominlist[j] - Rmaxlist[N - 2 - j]), dif)
	print(dif)


for _ in range(int(input())):
	num_ingredients = int(input())
	delish_values = list(map(int, input().split()))
	prefix_max = [0] * num_ingredients
	prefix_max[0] = delish_values[0]
	prefix_min = [0] * num_ingredients
	prefix_min[0] = delish_values[0]
	suffix_max = [0] * num_ingredients
	suffix_max[-1] = delish_values[-1]
	suffix_min = [0] * num_ingredients
	suffix_min[-1] = delish_values[-1]
	for i in range(1, num_ingredients):
		prefix_max[i] = max(prefix_max[i - 1] + delish_values[i], delish_values[i])
		prefix_min[i] = min(prefix_min[i - 1] + delish_values[i], delish_values[i])
		suffix_max[num_ingredients - 1 - i] = max(suffix_max[num_ingredients - i] + delish_values[num_ingredients - 1 - i], delish_values[num_ingredients - 1 - i])
		suffix_min[num_ingredients - 1 - i] = min(suffix_min[num_ingredients - i] + delish_values[num_ingredients - 1 - i], delish_values[num_ingredients - 1 - i])
	for i in range(1, num_ingredients):
		prefix_max[i] = max(prefix_max[i], prefix_max[i - 1])
		prefix_min[i] = min(prefix_min[i], prefix_min[i - 1])
		suffix_max[num_ingredients - 1 - i] = max(suffix_max[num_ingredients - 1 - i], suffix_max[num_ingredients - i])
		suffix_min[num_ingredients - 1 - i] = min(suffix_min[num_ingredients - 1 - i], suffix_min[num_ingredients - i])
	max_delish = max(prefix_max[0] - suffix_min[1], suffix_max[num_ingredients - 1] - prefix_min[num_ingredients - 2])
	for i in range(1, num_ingredients - 1):
		max_delish = max(max_delish, abs(prefix_max[i] - suffix_min[i + 1]), abs(suffix_max[i] - prefix_min[i - 1]))
	print(max_delish)


from sys import stdin
n = int(stdin.readline())
for _ in range(n):
	total = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	rightmax = [0] * total
	leftmax = [0] * total
	rightmin = [0] * total
	leftmin = [0] * total
	rightmax[0] = arr[0]
	leftmax[-1] = arr[-1]
	rightmin[0] = arr[0]
	leftmin[-1] = arr[-1]
	for i in range(1, total):
		rightmax[i] = max(arr[i], rightmax[i - 1] + arr[i])
		rightmin[i] = min(arr[i], rightmin[i - 1] + arr[i])
	for i in range(total - 2, -1, -1):
		leftmax[i] = max(arr[i], leftmax[i + 1] + arr[i])
		leftmin[i] = min(arr[i], leftmin[i + 1] + arr[i])
	max1 = float('-inf')
	i = 0
	while i + 1 < total:
		diff = abs(rightmax[i] - leftmin[i + 1])
		diff1 = abs(leftmax[i + 1] - rightmin[i])
		max1 = max(max1, diff, diff1)
		i += 1
	print(max1)


from sys import stdin
n = int(stdin.readline())
for _ in range(n):
	total = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	rightmax = [0] * total
	leftmax = [0] * total
	rightmin = [0] * total
	leftmin = [0] * total
	rightmax[0] = arr[0]
	leftmax[-1] = arr[-1]
	rightmin[0] = arr[0]
	leftmin[-1] = arr[-1]
	for i in range(1, total):
		rightmax[i] = max(arr[i], rightmax[i - 1] + arr[i])
		rightmin[i] = min(arr[i], rightmin[i - 1] + arr[i])
	for i in range(total - 2, -1, -1):
		leftmax[i] = max(arr[i], leftmax[i + 1] + arr[i])
		leftmin[i] = min(arr[i], leftmin[i + 1] + arr[i])
	max1 = []
	i = 0
	for i in range(total - 1):
		max1.append(abs(rightmax[i] - leftmin[i + 1]))
		max1.append(abs(leftmax[i + 1] - rightmin[i]))
	print(max(max1))


def cal():
	(maxdp1, maxdp1[0]) = ([0] * n, d[0])
	(maxdp2, maxdp2[-1]) = ([0] * n, d[-1])
	(mindp1, mindp1[0]) = ([0] * n, d[0])
	(mindp2, mindp2[-1]) = ([0] * n, d[-1])
	for i in range(n - 2, -1, -1):
		if maxdp2[i + 1] + d[i] > d[i]:
			maxdp2[i] = maxdp2[i + 1] + d[i]
		else:
			maxdp2[i] = d[i]
		if mindp2[i + 1] + d[i] < d[i]:
			mindp2[i] = mindp2[i + 1] + d[i]
		else:
			mindp2[i] = d[i]
	for i in range(1, n):
		if maxdp1[i - 1] + d[i] > d[i]:
			maxdp1[i] = maxdp1[i - 1] + d[i]
		else:
			maxdp1[i] = d[i]
		if mindp1[i - 1] + d[i] < d[i]:
			mindp1[i] = mindp1[i - 1] + d[i]
		else:
			mindp1[i] = d[i]
	ans = 0
	for i in range(1, n):
		ans = max(ans, abs(maxdp2[i] - mindp1[i - 1]), abs(mindp2[i] - maxdp1[i - 1]))
	return ans
for _ in range(int(input())):
	n = int(input())
	d = list(map(int, input().split()))
	print(cal())


def mp():
	return map(int, input().split(' '))

def lst():
	return list(mp())

def subsm(el, e):
	ms = el[0]
	me = el[0]
	nw = [el[0] * e]
	for i in range(1, len(el)):
		ms = max(el[i], ms + el[i])
		me = max(me, ms)
		nw.append(me * e)
	return nw
for _ in range(int(input())):
	n = int(input())
	ar = lst()
	nar = [-1 * ar[i] for i in range(n)]
	pmxf = subsm(ar, 1)
	pmxl = subsm(ar[::-1], 1)
	pmnf = subsm(nar, -1)
	pmnl = subsm(nar[::-1], -1)
	pmxl = pmxl[::-1]
	pmnl = pmnl[::-1]
	print(max([max(abs(pmxf[i] - pmnl[i + 1]), abs(pmnf[i] - pmxl[i + 1])) for i in range(n - 1)]))


t = int(input())
for rep in range(t):
	n = int(input())
	d = list(map(int, input().split()))
	lmax = [0] * n
	lmax[0] = d[0]
	rmax = [0] * n
	rmax[n - 1] = d[n - 1]
	lmin = [0] * n
	lmin[0] = d[0]
	rmin = [0] * n
	rmin[n - 1] = d[n - 1]
	for i in range(1, n):
		lmin[i] = min(lmin[i - 1] + d[i], d[i])
		lmax[i] = max(lmax[i - 1] + d[i], d[i])
	for i in range(n - 2, -1, -1):
		rmin[i] = min(rmin[i + 1] + d[i], d[i])
		rmax[i] = max(rmax[i + 1] + d[i], d[i])
	maxi1 = 0
	maxi2 = 0
	for i in range(n - 1):
		maxi1 = max(maxi1, abs(lmin[i] - rmax[i + 1]))
		maxi2 = max(maxi2, abs(lmax[i] - rmin[i + 1]))
	print(max(maxi1, maxi2))


class node:

	def __init__(self, size, elements):
		self.size = size
		self.elements = elements

def solve(inputs, size):
	maxr = [0] * size
	maxl = [0] * size
	minr = [0] * size
	minl = [0] * size
	maxl[0] = minl[0] = inputs[0]
	maxr[size - 1] = minr[size - 1] = inputs[size - 1]
	for i in range(1, size):
		maxl[i] = max(maxl[i - 1] + inputs[i], inputs[i])
		minl[i] = min(minl[i - 1] + inputs[i], inputs[i])
	for i in range(size - 2, -1, -1):
		maxr[i] = max(maxr[i + 1] + inputs[i], inputs[i])
		minr[i] = min(minr[i + 1] + inputs[i], inputs[i])
	result = []
	for i in range(size - 1):
		result.append(abs(maxl[i] - minr[i + 1]))
		result.append(abs(minl[i] - maxr[i + 1]))
	return max(result)
t = int(input())
inputs = []
for i in range(t):
	inputs.append(node(int(input()), list(map(int, input().split()))))
for i in inputs:
	print(solve(i.elements, i.size))


def calc(arr, n):
	ans = -10 ** 20
	dp = [0] * n
	dp[0] = arr[0]
	dp2 = [10 ** 20] * n
	dp2[n - 1] = arr[n - 1]
	for i in range(1, n):
		dp[i] = max(arr[i], arr[i] + dp[i - 1])
	for i in range(n - 2, -1, -1):
		dp2[i] = min(arr[i], arr[i] + dp2[i + 1])
	maxPref = [0] * n
	minSuff = [0] * n
	maxPref[0] = dp[0]
	minSuff[n - 1] = dp2[n - 1]
	for i in range(1, n):
		maxPref[i] = max(dp[i], maxPref[i - 1])
	for i in range(n - 2, -1, -1):
		minSuff[i] = min(dp2[i], minSuff[i + 1])
	for i in range(n - 1):
		ans = max(ans, abs(maxPref[i] - minSuff[i + 1]))
	return ans
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	res = max(calc(arr, n), calc(arr[::-1], n))
	print(res)


T = int(input())
output = []
(srmax, hlmin, hrmax) = ({}, {}, {})
(slmax, hrmin, hlmax) = ({}, {}, {})

def hard_left_min(array, j):
	if j == 0:
		return array[0]
	elif j in hlmin:
		return hlmin[j]
	else:
		tmp = min(array[j], hard_left_min(array, j - 1) + array[j])
		hlmin[j] = tmp
		return tmp

def soft_right_max(array, j):
	N = len(array)
	if j == N - 1:
		return array[N - 1]
	elif j in srmax:
		return srmax[j]
	else:
		tmp = max(hard_right_max(array, j), soft_right_max(array, j + 1))
		srmax[j] = tmp
		return tmp

def hard_right_max(array, j):
	N = len(array)
	if j == N - 1:
		return array[N - 1]
	elif j in hrmax:
		return hrmax[j]
	else:
		tmp = max(array[j], array[j] + hard_right_max(array, j + 1))
		hrmax[j] = tmp
		return tmp

def hard_right_min(array, j):
	N = len(array)
	if j == N - 1:
		return array[j]
	elif j in hrmin:
		return hrmin[j]
	else:
		tmp = min(array[j], array[j] + hard_right_min(array, j + 1))
		hrmin[j] = tmp
		return tmp

def soft_left_max(array, j):
	if j == 0:
		return array[0]
	elif j in slmax:
		return slmax[j]
	else:
		tmp = max(hard_left_max(array, j), soft_left_max(array, j - 1))
		slmax[j] = tmp
		return tmp

def hard_left_max(array, j):
	if j == 0:
		return array[0]
	elif j in hlmax:
		return hlmax[j]
	else:
		tmp = max(array[j], hard_left_max(array, j - 1) + array[j])
		hlmax[j] = tmp
		return tmp
for _ in range(T):
	N = int(input())
	D = list(map(int, input().split()))
	for j in range(N):
		hard_left_min(D, j)
	for j in range(N - 1, -1, -1):
		hard_right_max(D, j)
	for j in range(N - 1, -1, -1):
		soft_right_max(D, j)
	for j in range(N - 1, -1, -1):
		hard_right_min(D, j)
	for j in range(N):
		hard_left_max(D, j)
	for j in range(N):
		soft_left_max(D, j)
	max_delish = -1
	for j in range(N):
		if j < N - 1:
			max_delish = max(max_delish, soft_right_max(D, j + 1) - hard_left_min(D, j), soft_left_max(D, j) - hard_right_min(D, j + 1))
	output.append(max_delish)
	(srmax, hlmin, hrmax) = ({}, {}, {})
	(slmax, hrmin, hlmax) = ({}, {}, {})
for o in output:
	print(o)


def delish(arr, n):
	minpref = [0 for _ in range(n)]
	maxpref = [0 for _ in range(n)]
	minsuf = [0 for _ in range(n)]
	maxsuf = [0 for _ in range(n)]
	minpref[0] = maxpref[0] = arr[0]
	(curmax, curmin) = (arr[0], arr[0])
	for i in range(1, n):
		curmax = max(curmax + arr[i], arr[i])
		curmin = min(curmin + arr[i], arr[i])
		maxpref[i] = max(maxpref[i - 1], curmax)
		minpref[i] = min(minpref[i - 1], curmin)
	minsuf[n - 1] = maxsuf[n - 1] = arr[n - 1]
	(curmax, curmin) = (arr[n - 1], arr[n - 1])
	for i in range(n - 2, -1, -1):
		curmax = max(curmax + arr[i], arr[i])
		curmin = min(curmin + arr[i], arr[i])
		maxsuf[i] = max(maxsuf[i + 1], curmax)
		minsuf[i] = min(minsuf[i + 1], curmin)
	m = float('-inf')
	for i in range(n - 1):
		r = max(abs(maxpref[i] - minsuf[i + 1]), abs(minpref[i] - maxsuf[i + 1]))
		if r > m:
			m = r
	return m
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(delish(arr, n))


T = int(input())
for j in range(T):
	N = int(input())
	a = list(map(int, input().split()))
	max1 = a[:]
	max2 = a[:]
	min1 = a[:]
	min2 = a[:]
	t = 0
	for i in range(1, N):
		max1[i] = max(max1[i - 1] + a[i], a[i])
		min1[i] = min(min1[i - 1] + a[i], a[i])
	for i in range(N - 2, -1, -1):
		max2[i] = max(max2[i + 1] + a[i], a[i])
		min2[i] = min(min2[i + 1] + a[i], a[i])
	for i in range(N - 1):
		t = max(t, abs(min1[i] - max2[i + 1]))
		t = max(t, abs(max1[i] - min2[i + 1]))
	print(t)


import sys
import copy
import math
import heapq
import bisect
import random
import operator
import statistics
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from heapq import heapify, heappush, heappop
from itertools import permutations, combinations
from collections import Counter, OrderedDict, deque
from bisect import bisect_left as bl, bisect_right as br
from functools import lru_cache, reduce
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strr = lambda : input().strip()
jl = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
muli = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().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))
mod = 1000000007
for i in range(int(input())):
	n = int(input())
	d = list(map(int, input().split()))
	(o1, o2, r1, r2) = ([], [], [], [])
	(m1, m2, p1, p2) = (d[0], d[0], d[-1], d[-1])
	(l1, l2, l3, l4) = (0, 0, 0, 0)
	for j in range(n):
		l1 += d[j]
		l2 += d[j]
		l3 += d[-j - 1]
		l4 += d[-j - 1]
		if l1 > m1:
			m1 = l1
		if l2 < m2:
			m2 = l2
		if l3 > p1:
			p1 = l3
		if l4 < p2:
			p2 = l4
		o1.append(m1)
		o2.append(m2)
		r1.append(p1)
		r2.append(p2)
		if l1 < 0:
			l1 = 0
		if l2 > 0:
			l2 = 0
		if l3 < 0:
			l3 = 0
		if l4 > 0:
			l4 = 0
	c = 0
	for k in range(n - 1):
		c = max(abs(o1[k] - r2[n - 2 - k]), abs(o2[k] - r1[n - 2 - k]), c)
	print(c)


n = int(input())
for _ in range(n):
	total = int(input())
	arr = list(map(int, input().split()))
	rightmax = [0] * total
	leftmax = [0] * total
	rightmin = [0] * total
	leftmin = [0] * total
	rightmax[0] = arr[0]
	leftmax[-1] = arr[-1]
	rightmin[0] = arr[0]
	leftmin[-1] = arr[-1]
	for i in range(1, total):
		rightmax[i] = max(arr[i], rightmax[i - 1] + arr[i])
		rightmin[i] = min(arr[i], rightmin[i - 1] + arr[i])
	for i in range(total - 2, -1, -1):
		leftmax[i] = max(arr[i], leftmax[i + 1] + arr[i])
		leftmin[i] = min(arr[i], leftmin[i + 1] + arr[i])
	max1 = []
	i = 0
	while i + 1 < total:
		max1.append(abs(rightmax[i] - leftmin[i + 1]))
		max1.append(abs(leftmax[i + 1] - rightmin[i]))
		i += 1
	print(max(max1))


from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	ln = [0] * n
	ln[0] = a[0]
	lx = [0] * n
	lx[0] = a[0]
	rn = [0] * n
	rn[n - 1] = a[n - 1]
	rx = [0] * n
	rx[n - 1] = a[n - 1]
	for i in range(1, n):
		ln[i] = min(ln[i - 1] + a[i], a[i])
		lx[i] = max(lx[i - 1] + a[i], a[i])
		rn[n - 1 - i] = min(rn[n - i] + a[n - 1 - i], a[n - 1 - i])
		rx[n - 1 - i] = max(rx[n - i] + a[n - 1 - i], a[n - 1 - i])
	ans = max(lx[0] - rn[1], rx[n - 1] - ln[n - 2])
	for i in range(1, n - 1):
		ans = max(ans, lx[i] - rn[i + 1], rx[i] - ln[i - 1])
	print(ans)


def cal():

	def max_delish2(idx):
		nonlocal maxdp2
		if idx == n - 1:
			maxdp2[idx] = d[idx]
			return maxdp2[idx]
		temp = max_delish2(idx + 1)
		if temp + d[idx] > d[idx]:
			maxdp2[idx] = temp + d[idx]
		else:
			maxdp2[idx] = d[idx]
		return maxdp2[idx]

	def max_delish1(idx):
		nonlocal maxdp1
		if idx == 0:
			maxdp1[idx] = d[idx]
			return maxdp1[idx]
		temp = max_delish1(idx - 1)
		if temp + d[idx] > d[idx]:
			maxdp1[idx] = temp + d[idx]
		else:
			maxdp1[idx] = d[idx]
		return maxdp1[idx]

	def min_delish2(idx):
		nonlocal mindp2
		if idx == n - 1:
			mindp2[idx] = d[idx]
			return mindp2[idx]
		temp = min_delish2(idx + 1)
		if temp + d[idx] < d[idx]:
			mindp2[idx] = temp + d[idx]
		else:
			mindp2[idx] = d[idx]
		return mindp2[idx]

	def min_delish1(idx):
		nonlocal mindp1
		if idx == 0:
			mindp1[idx] = d[idx]
			return mindp1[idx]
		temp = min_delish1(idx - 1)
		if temp + d[idx] < d[idx]:
			mindp1[idx] = temp + d[idx]
		else:
			mindp1[idx] = d[idx]
		return mindp1[idx]
	(maxdp1, maxdp1[0]) = ([0] * n, d[0])
	(maxdp2, maxdp2[-1]) = ([0] * n, d[-1])
	(mindp1, mindp1[0]) = ([0] * n, d[0])
	(mindp2, mindp2[-1]) = ([0] * n, d[-1])
	for i in range(n - 2, -1, -1):
		if maxdp2[i + 1] + d[i] > d[i]:
			maxdp2[i] = maxdp2[i + 1] + d[i]
		else:
			maxdp2[i] = d[i]
		if mindp2[i + 1] + d[i] < d[i]:
			mindp2[i] = mindp2[i + 1] + d[i]
		else:
			mindp2[i] = d[i]
	for i in range(1, n):
		if maxdp1[i - 1] + d[i] > d[i]:
			maxdp1[i] = maxdp1[i - 1] + d[i]
		else:
			maxdp1[i] = d[i]
		if mindp1[i - 1] + d[i] < d[i]:
			mindp1[i] = mindp1[i - 1] + d[i]
		else:
			mindp1[i] = d[i]
	ans = 0
	for i in range(1, n):
		ans = max(ans, abs(maxdp2[i] - mindp1[i - 1]), abs(mindp2[i] - maxdp1[i - 1]))
	return ans
for _ in range(int(input())):
	n = int(input())
	d = list(map(int, input().split()))
	print(cal())


for tests in range(int(input())):
	N = int(input())
	D = list(map(int, input().split()))
	minL = []
	minR = []
	maxL = []
	maxR = []
	currentMax = currentMin = 0
	for i in range(N - 1):
		if i == 0:
			if D[i] < 0:
				currentMin = D[i]
			else:
				currentMax = D[i]
			minL.append(D[i])
			maxL.append(D[i])
			continue
		currentMax = max(currentMax + D[i], D[i])
		currentMin = min(currentMin + D[i], D[i])
		minL.append(min(currentMin, minL[-1]))
		maxL.append(max(currentMax, maxL[-1]))
	currentMax = currentMin = 0
	for i in range(N - 1, 0, -1):
		if i == N - 1:
			if D[i] < 0:
				currentMin = D[i]
			else:
				currentMax = D[i]
			minR.append(D[i])
			maxR.append(D[i])
			continue
		currentMax = max(currentMax + D[i], D[i])
		currentMin = min(currentMin + D[i], D[i])
		maxR.append(max(currentMax, maxR[-1]))
		minR.append(min(currentMin, minR[-1]))
	minR.reverse()
	maxR.reverse()
	maxAbs = 0
	for i in range(N - 1):
		maxAbs = max(max(abs(minL[i] - maxR[i]), abs(maxL[i] - minR[i])), maxAbs)
	print(maxAbs)


def leftMin(a, n):
	r = []
	minSum = a[0]
	curSum = 0
	i = 0
	while i < n - 1:
		if curSum >= 0:
			curSum = a[i]
		else:
			curSum += a[i]
		if minSum > curSum:
			minSum = curSum
		r.append(minSum)
		i += 1
	return r

def rightMin(a, n):
	r = []
	minSum = a[-1]
	curSum = 0
	i = n - 1
	while i > 0:
		if curSum >= 0:
			curSum = a[i]
		else:
			curSum += a[i]
		if minSum > curSum:
			minSum = curSum
		r.insert(0, minSum)
		i -= 1
	return r

def leftMax(a, n):
	r = []
	maxSum = a[0]
	curSum = 0
	i = 0
	while i < n - 1:
		if curSum <= 0:
			curSum = 0
		curSum += a[i]
		if maxSum < curSum:
			maxSum = curSum
		r.append(maxSum)
		i += 1
	return r

def rightMax(a, n):
	r = []
	maxSum = a[-1]
	curSum = 0
	i = n - 1
	while i > 0:
		if curSum <= 0:
			curSum = 0
		curSum += a[i]
		if maxSum < curSum:
			maxSum = curSum
		r.insert(0, maxSum)
		i -= 1
	return r
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	leftMinSeq = leftMin(a, n)
	leftMaxSeq = leftMax(a, n)
	rightMinSeq = rightMin(a, n)
	rightMaxSeq = rightMax(a, n)
	ans = [abs(leftMaxSeq[i] - rightMinSeq[i]) for i in range(n - 1)]
	ans.extend([abs(leftMinSeq[i] - rightMaxSeq[i]) for i in range(n - 1)])
	print(max(ans))


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	(max_lr, min_lr) = ([a[0]], [a[0]])
	for i in range(1, n):
		max_lr.append(max(max_lr[i - 1] + a[i], a[i]))
		min_lr.append(min(min_lr[i - 1] + a[i], a[i]))
	max_rl = [0 for i in range(n)]
	min_rl = [0 for i in range(n)]
	max_inc_rl = [0 for i in range(n)]
	min_inc_rl = [0 for i in range(n)]
	max_rl[n - 1] = a[n - 1]
	min_rl[n - 1] = a[n - 1]
	max_inc_rl[n - 1] = a[n - 1]
	min_inc_rl[n - 1] = a[n - 1]
	for i in range(n - 2, -1, -1):
		max_inc_rl[i] = max(max_inc_rl[i + 1] + a[i], a[i])
		max_rl[i] = max(max_inc_rl[i], max_rl[i + 1])
		min_inc_rl[i] = min(min_inc_rl[i + 1] + a[i], a[i])
		min_rl[i] = min(min_inc_rl[i], min_rl[i + 1])
	dishes = [max(abs(max_lr[i] - min_rl[i + 1]), abs(min_lr[i] - max_rl[i + 1])) for i in range(n - 1)]
	print(max(dishes))


for _ in range(int(input())):
	N = int(input())
	a = list(map(int, input().split()))[::-1]
	mxsfr = [0] * N
	mv = float('-inf')
	tmv = 0
	for i in range(N):
		tmv = tmv + a[i]
		if mv < tmv:
			mv = tmv
		if tmv < 0:
			tmv = 0
		mxsfr[-i - 1] = mv
	mn = float('inf')
	tmn = 0
	mnsfr = [0] * N
	for i in range(N):
		tmn = tmn + a[i]
		if mn > tmn:
			mn = tmn
		if tmn > 0:
			tmn = 0
		mnsfr[-i - 1] = mn
	a = a[::-1]
	mn = float('inf')
	tmn = 0
	mnsf = [0] * N
	for i in range(N):
		tmn = tmn + a[i]
		if mn > tmn:
			mn = tmn
		if tmn > 0:
			tmn = 0
		mnsf[i] = mn
	mxsf = [0] * N
	mv = float('-inf')
	tmv = 0
	for i in range(N):
		tmv = tmv + a[i]
		if mv < tmv:
			mv = tmv
		if tmv < 0:
			tmv = 0
		mxsf[i] = mv
	ans = 0
	for i in range(N - 1):
		if abs(mnsf[i] - mxsfr[i + 1]) > ans:
			ans = abs(mnsf[i] - mxsfr[i + 1])
		if abs(mxsf[i] - mnsfr[i + 1]) > ans:
			ans = abs(mxsf[i] - mnsfr[i + 1])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	Ar = A[::-1]
	dpmax = [A[i] for i in range(n)]
	dpmin = [Ar[i] for i in range(n)]
	for i in range(1, n):
		dpmax[i] = max(A[i], dpmax[i - 1] + A[i])
	for i in range(1, n):
		dpmin[i] = min(Ar[i], dpmin[i - 1] + Ar[i])
	dpmin = dpmin[::-1]
	for i in range(1, n):
		dpmax[i] = max(dpmax[i - 1], dpmax[i])
	ans = dpmax[0] - dpmin[1]
	for i in range(n - 1):
		ans = max(ans, dpmax[i] - dpmin[i + 1])
	dpmax = [Ar[i] for i in range(n)]
	dpmin = [A[i] for i in range(n)]
	for i in range(1, n):
		dpmax[i] = max(Ar[i], dpmax[i - 1] + Ar[i])
	dpmax = dpmax[::-1]
	for i in range(1, n):
		dpmin[i] = min(A[i], dpmin[i - 1] + A[i])
	for i in range(1, n):
		dpmin[i] = min(dpmin[i - 1], dpmin[i])
	for i in range(n - 1):
		ans = max(ans, dpmax[i + 1] - dpmin[i])
	print(ans)


def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	hardLeftMin = []
	for i in range(n):
		if i == 0:
			hardLeftMin.append(arr[i])
		else:
			hardLeftMin.append(min(hardLeftMin[-1] + arr[i], arr[i]))
	hardLeftMax = []
	for i in range(n):
		if i == 0:
			hardLeftMax.append(arr[i])
		else:
			hardLeftMax.append(max(hardLeftMax[-1] + arr[i], arr[i]))
	softLeftMin = []
	for i in range(n):
		if i == 0:
			softLeftMin.append(hardLeftMin[i])
		else:
			softLeftMin.append(min(softLeftMin[-1], hardLeftMin[i]))
	softLeftMax = []
	for i in range(n):
		if i == 0:
			softLeftMax.append(hardLeftMax[i])
		else:
			softLeftMax.append(max(softLeftMax[-1], hardLeftMax[i]))
	hardRightMin = []
	for i in range(n - 1, -1, -1):
		if i == n - 1:
			hardRightMin.append(arr[i])
		else:
			hardRightMin.append(min(hardRightMin[-1] + arr[i], arr[i]))
	hardRightMin = list(reversed(hardRightMin))
	hardRightMax = []
	for i in range(n - 1, -1, -1):
		if i == n - 1:
			hardRightMax.append(arr[i])
		else:
			hardRightMax.append(max(hardRightMax[-1] + arr[i], arr[i]))
	hardRightMax = list(reversed(hardRightMax))
	ans = 0
	for i in range(n - 1):
		ans = max(ans, softLeftMax[i] - hardRightMin[i + 1])
		ans = max(ans, hardRightMax[i + 1] - softLeftMin[i])
	print(ans)
for t in range(int(input())):
	solve()


def kadane(a):
	b = [a[0]]
	b1 = [a[0]]
	cs = a[0]
	cs1 = a[0]
	for i in range(1, len(a)):
		cs = max(a[i], cs + a[i])
		cs1 = min(a[i], cs1 + a[i])
		b.append(max(cs, b[-1]))
		b1.append(min(cs1, b1[-1]))
	return (b, b1)

def kadane1(a):
	(b, b1) = ([0] * len(a), [0] * len(a))
	b[-1] = b1[-1] = a[-1]
	cs = cs1 = a[-1]
	for i in range(len(a) - 2, -1, -1):
		cs = min(a[i], cs + a[i])
		cs1 = max(a[i], cs1 + a[i])
		b[i] = min(cs, b[i + 1])
		b1[i] = max(cs1, b[i + 1])
	return (b, b1)
for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	(x, y) = kadane(a)
	(z, w) = kadane1(a)
	mx = 0
	for i in range(n - 1):
		mx = max(mx, abs(x[i] - z[i + 1]), abs(y[i] - w[i + 1]))
	print(mx)


import math

def maxsumsub(l):
	ans = []
	mx_1 = -1 * math.inf
	mx_2 = 0
	for i in range(len(l)):
		mx_2 += l[i]
		if mx_1 < mx_2:
			mx_1 = mx_2
		if mx_2 < 0:
			mx_2 = 0
		ans.append(mx_1)
	return ans

def minsumsub(l):
	ans = []
	mi_1 = math.inf
	mi_2 = 0
	for i in range(len(l)):
		mi_2 += l[i]
		if mi_1 > mi_2:
			mi_1 = mi_2
		if mi_2 > 0:
			mi_2 = 0
		ans.append(mi_1)
	return ans

def maxsumsubrev(l):
	ans = []
	mx_1 = -1 * math.inf
	mx_2 = 0
	for i in range(len(l) - 1, -1, -1):
		mx_2 += l[i]
		if mx_1 < mx_2:
			mx_1 = mx_2
		if mx_2 < 0:
			mx_2 = 0
		ans.insert(0, mx_1)
	return ans

def minsumsubrev(l):
	ans = []
	mi_1 = math.inf
	mi_2 = 0
	for i in range(len(l) - 1, -1, -1):
		mi_2 += l[i]
		if mi_1 > mi_2:
			mi_1 = mi_2
		if mi_2 > 0:
			mi_2 = 0
		ans.insert(0, mi_1)
	return ans
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	max_i = maxsumsub(l)
	i_max = maxsumsubrev(l)
	min_i = minsumsub(l)
	i_min = minsumsubrev(l)
	ans = -1
	for i in range(len(l) - 1):
		t_1 = abs(max_i[i] - i_min[i + 1])
		t_2 = abs(min_i[i] - i_max[i + 1])
		t_3 = max(t_1, t_2)
		if ans < t_3:
			ans = t_3
	print(ans)