JJ has an array A of length N. He can perform the following operation on A:
Select any L, R (1 ≤ L ≤ R ≤ N) and for each i such that L ≤ i ≤ R, set A_{i} := A_{i} + 1.

JJ wants to make A palindromic. Find the minimum number of moves to do so.

Note: An array is called a palindrome if it reads the same backwards and forwards, for e.g. [1, 3, 3, 1] and [6, 2, 6] are palindromic.

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N — the size of the array A.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.

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

For each test case, output the minimum number of moves to make A palindromic.

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

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

----- Sample Input 1 ------ 
3
6
2 6 4 3 4 1
2
1 10
3
1 10 1

----- Sample Output 1 ------ 
2
9
0

----- explanation 1 ------ 
Test Case 1: We can perform the following operations: 
- $[2, 6, \underline{4, 3, 4, 1}] \xrightarrow{L = 3, R = 6} [2, 6, 5, 4, 5, 2]$
- $[2, 6, 5, \underline{4, 5}, 2] \xrightarrow{L = 4, R = 5} [2, 6, 5, 5, 6, 2]$

Test Case 2: We perform the operation on $(L = 1, R = 1)$ $9$ times after which array becomes $[10, 10]$.

Test Case 3: $A$ is already a palindrome.

Difficulty: VERY_HARD
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	cur = res = 0
	for i in range(n):
		need = max(0, arr[n - 1 - i] - arr[i])
		res += max(0, need - cur)
		cur = need
	print(res)


from functools import reduce

def check(a, b):
	if a > 0 and b > 0 or (a <= 0 and b <= 0):
		return True
	return False
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	diff = [0 for _ in range(0, len(a))]
	for i in range(len(a)):
		if a[i] < a[n - i - 1]:
			diff[i] = a[n - i - 1] - a[i]
	m = diff[0]
	for i in range(1, n):
		m += max(0, diff[i] - diff[i - 1])
	print(m)


iterate = int(input())
for _ in range(iterate):
	length = int(input())
	array = input().split(' ')
	array = [int(x) for x in array]
	diff = [0 for _ in range(0, len(array))]
	for i in range(int(len(array))):
		if array[i] < array[length - i - 1]:
			if array[length - i - 1] > array[i]:
				diff[i] = array[length - i - 1] - array[i]
	ans = diff[0]
	for i in range(1, length):
		ans = ans + max(0, diff[i] - diff[i - 1])
	print(ans)


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	arr = list(map(int, input().split()))
	diff = [0 for _ in range(0, len(arr))]
	for i in range(0, n):
		if arr[i] < arr[n - i - 1]:
			diff[i] = arr[n - i - 1] - arr[i]
	ans = diff[0]
	for i in range(1, n):
		ans = ans + max(0, diff[i] - diff[i - 1])
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	diff = n * [0]
	for i in range(n):
		if a[i] < a[n - i - 1]:
			diff[i] = a[n - i - 1] - a[i]
	i = 1
	count = diff[0]
	while i < n:
		count = count + max(0, diff[i] - diff[i - 1])
		i = i + 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	a = [0 for i in range(n)]
	i = 0
	j = n - 1
	while i < j:
		if arr[i] < arr[j]:
			a[i] = arr[j] - arr[i]
		else:
			a[j] = arr[i] - arr[j]
		i += 1
		j -= 1
	cnt = a[0]
	for i in range(n - 1):
		cnt += (a[i + 1] - a[i]) * int(a[i + 1] > a[i])
	print(cnt)


import math
import sys
import random
searches = int(sys.stdin.readline())

def cnt_chng(A, K):
	max_l = 0
	max_r = 0
	count_chng = 0
	if K % 2 == 0:
		hlf_dwy = K // 2
	else:
		hlf_dwy = K // 2 + 1
	for i in range(hlf_dwy):
		if A[i] > A[K - 1 - i]:
			max_r = 0
			if max_l <= A[i] - A[K - 1 - i]:
				count_chng += A[i] - A[K - 1 - i] - max_l
				max_l = A[i] - A[K - 1 - i]
			else:
				max_l = A[i] - A[K - 1 - i]
		if A[i] == A[K - 1 - i]:
			count_chng += 0
			max_r = 0
			max_l = 0
		if A[i] < A[K - 1 - i]:
			max_l = 0
			if max_r <= -(A[i] - A[K - 1 - i]):
				count_chng += -(A[i] - A[K - 1 - i]) - max_r
				max_r = -(A[i] - A[K - 1 - i])
			else:
				max_r = -(A[i] - A[K - 1 - i])
	return count_chng
for i in range(searches):
	num = int(sys.stdin.readline())
	bounds = sys.stdin.readline()
	a_list = list(map(int, bounds.split()))
	print(cnt_chng(a_list, num))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	diff = [0] * n
	for i in range(n):
		if l[i] != l[-(i + 1)]:
			diff[i] = (l[i] - l[-(i + 1)]) * (-1 if l[-(i + 1)] > l[i] else 0)
	ans = diff[0]
	for i in range(1, n):
		ans += max(0, diff[i] - diff[i - 1])
	print(ans)


from collections import defaultdict
import math as mt
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	ans = [0 for i in range(n)]
	i = 0
	j = n - 1
	while i < j:
		if a[i] < a[j]:
			ans[i] = a[j] - a[i]
		else:
			ans[j] = a[i] - a[j]
		i += 1
		j -= 1
	cnt = ans[0]
	for i in range(n - 1):
		cnt += (ans[i + 1] - ans[i]) * int(ans[i + 1] > ans[i])
	print(cnt)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	ar = [l[i] - l[n - i - 1] for i in range(n // 2)]
	(res, curr) = (0, 0)
	for i in ar:
		if i > 0:
			if curr >= 0:
				res += max(0, i - curr)
			else:
				res += i
		elif i < 0:
			if curr <= 0:
				res += max(0, curr - i)
			else:
				res += -i
		curr = i
	print(res)


t = int(input())
while t != 0:
	n = int(input())
	L = [int(i) for i in input().split()]
	i = 0
	j = n - 1
	ans = 0
	diff = [0 for i in range(n)]
	for i in range(n):
		p = L[n - i - 1] - L[i]
		if p > 0:
			diff[i] = p
	ans = diff[0]
	for i in range(1, len(diff)):
		ans += max(0, diff[i] - diff[i - 1])
	print(ans)
	t = t - 1


for _ in range(int(input())):
	length = int(input())
	arr = list(map(int, input().split()))
	cur = ans = 0
	for i in range(length):
		prevdiff = max(0, arr[length - 1 - i] - arr[i])
		ans += max(0, prevdiff - cur)
		cur = prevdiff
	print(ans)


T = int(input())
for _ in range(T):
	N = int(input())
	L = list(map(int, input().split()))
	diff = []
	for i in range(N):
		(x, y) = (L[i], L[N - 1 - i])
		if x > y:
			diff.append(x - y)
		else:
			diff.append(0)
	diff.append(0)
	t = 0
	for i in range(N):
		t += max(0, diff[i] - diff[i + 1])
	print(t)


t = int(input())

def solution(a, n):
	b = []
	for i in range(n):
		c = a[i] - a[n - 1 - i]
		if c < 0:
			b.append(abs(c))
		else:
			b.append(0)
	ans = b[0]
	for i in range(1, n):
		ans += max(0, b[i] - b[i - 1])
	return ans
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	print(solution(arr, n))
	t -= 1


import numpy as np
T = int(input())
for t in range(T):
	N = int(input())
	A = np.array(list(map(int, input().split(' '))))
	diff = np.maximum(A - np.flip(A), np.zeros(N))
	count = 0
	local_max = 0
	decrease = False
	prec = 0
	carying = 0
	for i in range(N):
		if diff[i] < prec:
			decrease = True
		elif diff[i] > prec and decrease:
			count += local_max - carying
			local_max = diff[i]
			carying = prec
			decrease = False
		else:
			local_max = max(local_max, diff[i])
		prec = diff[i]
	print(int(count + local_max - carying))


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


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = [0 for i in range(n)]
	(i, j) = (0, n - 1)
	while i < j:
		if l[i] < l[j]:
			d[i] = l[j] - l[i]
		else:
			d[j] = l[i] - l[j]
		i += 1
		j -= 1
	ans = d[0]
	for i in range(1, n):
		ans += max(0, d[i] - d[i - 1])
	print(ans)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = [0] * n
	for i in range(n // 2):
		val = l[i] - l[n - 1 - i]
		if val < 0:
			l1[i] = -val
		else:
			l1[n - 1 - i] = val
	if n % 2 != 0:
		l1.pop(n // 2)
	count = l1[0]
	for i in range(1, len(l1)):
		if l1[i] - l1[i - 1] > 0:
			count += l1[i] - l1[i - 1]
	print(count)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	cur = ans = 0
	for i in range(n):
		need = max(0, a[n - 1 - i] - a[i])
		ans += max(0, need - cur)
		cur = need
	print(ans)


import sys
input = sys.stdin.readline

def print(*args, end='\n', sep=' ') -> None:
	sys.stdout.write(sep.join(map(str, args)) + end)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = [0] * n
	for i in range((n + 1) // 2):
		if a[i] > a[n - 1 - i]:
			b[n - i - 1] = a[i] - a[n - 1 - i]
		else:
			b[i] = -a[i] + a[n - 1 - i]
	prev = 0
	ans = 0
	for i in range(n):
		if b[i] < prev:
			prev = b[i]
		elif b[i] > prev:
			ans += b[i] - prev
			prev = b[i]
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	b = [0] * n
	for i in range(n):
		b[i] = max(ar[n - i - 1] - ar[i], 0)
	ans = b[0]
	for i in range(1, n):
		ans += max(0, b[i] - b[i - 1])
	print(ans)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	res = l = 0
	for i in range(n):
		m = max(0, a[i] - a[n - 1 - i])
		res += max(0, m - l)
		l = m
	print(res)


for t in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	ans = m = 0
	for i in range(n):
		need = max(0, a[n - i - 1] - a[i])
		ans += max(0, need - m)
		m = need
	print(ans)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	las = ans = 0
	for i in range(N):
		now = max(0, A[N - i - 1] - A[i])
		ans += max(0, now - las)
		las = now
	print(ans)


for _ in range(int(input())):
	x = int(input())
	arr = list(map(int, input().split()))
	cur = answer = 0
	for i in range(x):
		need = max(0, arr[x - 1 - i] - arr[i])
		answer += max(0, need - cur)
		cur = need
	print(answer)


import sys
import math as m
from collections import Counter

def gcd(a, b):
	return b if a % b == 0 else gcd(b, a % b)

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

def print_l(l):
	return [i for i in l]

def si():
	return input()

def isKthBitSet(n, k):
	return True if n & 1 << k - 1 else False

def A():
	(n, m, k, x) = map(int, input().split())
	ct = 1
	s = n
	while s <= x - 1:
		s += n
		ct += 1
		if ct % k == 0:
			s += m
	if ct % k == 0:
		return 'YES'
	else:
		return 'NO'

def B():
	s = input()
	if s[0] == s[-1]:
		return len(s) - 2
	else:
		return 2

def C():
	n = int(input())
	l = li()
	i = 0
	j = len(l) - 1
	ans = 0
	while i < j:
		if l[i] != l[j]:
			if l[i] < l[j]:
				l[j] = l[j] - l[i]
				i += 1
			else:
				l[i] = l[i] - l[j]
				j -= 1
			ans += 1
		else:
			i += 1
			j -= 1
	return ans

def D():
	n = int(input())
	a = li()
	cur = ans = 0
	for i in range(n):
		need = max(0, a[n - 1 - i] - a[i])
		ans += max(0, need - cur)
		cur = need
	return ans
for _ in range(int(input())):
	print(D())


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	for i in range(n):
		b.append(max(0, a[n - 1 - i] - a[i]))
	ans = b[0]
	for i in range(1, n):
		ans += max(0, b[i] - b[i - 1])
	print(ans)


n = int(input())
for n2 in range(n):
	n3 = int(input())
	a = input().split(' ')
	b = []
	c = 0
	for i in range(n3):
		b.append(0)
		if int(a[i]) < int(a[n3 - 1 - i]):
			b[-1] = int(a[n3 - 1 - i]) - int(a[i])
			if i > 0 and b[-1] > b[-2]:
				c += b[-1] - b[-2]
			elif i == 0:
				c += b[0]
	print(c)


def makePal(n, arr):
	curr = ans = 0
	for i in range(n):
		need = max(0, arr[n - 1 - i] - arr[i])
		ans += max(0, need - curr)
		curr = need
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	print(makePal(n, arr))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = c = 0
	for i in range(n):
		d = max(0, a[n - 1 - i] - a[i])
		c += max(0, d - b)
		b = d
	print(c)


for _ in range(int(input())):
	n = int(input())
	nlist = list(map(int, input().split()))
	tlist = []
	for i in range(n):
		tlist.append(max(0, nlist[n - 1 - i] - nlist[i]))
	ans = tlist[0]
	for i in range(1, n):
		ans += max(0, tlist[i] - tlist[i - 1])
	print(ans)


def solution(n, a):
	cost = [0] * n
	left = 0
	right = n - 1
	while left < right:
		if a[left] < a[right]:
			cost[left] = a[right] - a[left]
		elif a[left] > a[right]:
			cost[right] = a[left] - a[right]
		left += 1
		right -= 1
	dp = cost[0]
	for i in range(1, n):
		if cost[i] - cost[i - 1] < 0:
			continue
		dp += cost[i] - cost[i - 1]
	return dp
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))[:n]
	print(solution(n, a))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	i = 0
	j = n - 1
	ans = 0
	curr = 0
	for i in range(n):
		req = max(0, a[n - i - 1] - a[i])
		ans += max(0, req - curr)
		curr = req
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	if n % 2 == 1:
		a.pop(n // 2)
		n -= 1
	m = n // 2
	if n == 0:
		print(0)
	else:
		for i in range(n // 2):
			if a[i] == a[n - i - 1]:
				pass
			elif a[i] < a[n - i - 1]:
				for p in range(m):
					b = a[n - i - 1] - a[i]
					if a[i] == a[n - i - 1]:
						break
					else:
						for j in range(i, m):
							if a[j] < a[n - j - 1]:
								b = min(a[n - j - 1] - a[j], b)
							else:
								j -= 1
								break
						for k in range(i, j + 1):
							a[k] += b
						count += b
			elif a[i] > a[n - i - 1]:
				for p in range(m):
					b = a[i] - a[n - i - 1]
					if a[i] == a[n - i - 1]:
						break
					else:
						for j in range(n - i - 1, m - 1, -1):
							if a[j] < a[n - j - 1]:
								b = min(a[n - j - 1] - a[j], b)
							else:
								j += 1
								break
						for k in range(n - i - 1, j - 1, -1):
							a[k] += b
						count += b
		print(count)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	temp = [0 for _ in range(n)]
	start = 0
	end = n - 1
	while start < end:
		if arr[start] > arr[end]:
			temp[end] = arr[start] - arr[end]
		elif arr[start] < arr[end]:
			temp[start] = arr[end] - arr[start]
		start += 1
		end -= 1
	res = temp[0]
	for i in range(1, n):
		if temp[i] - temp[i - 1] <= 0:
			res += 0
		else:
			res += temp[i] - temp[i - 1]
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = o = 0
	for i in range(n):
		x = max(0, a[n - 1 - i] - a[i])
		o += max(0, x - c)
		c = x
	print(o)


j = int(input())
for k in range(j):
	n = int(input())
	l = list(map(int, input().split()))
	(s, t) = (0, 0)
	for i in range(len(l)):
		m = max(0, l[len(l) - 1 - i] - l[i])
		s += max(0, m - t)
		t = m
	print(s)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	dp = [0] * n
	l = 0
	r = len(arr) - 1
	while r >= l:
		if arr[l] != arr[r]:
			if arr[l] > arr[r]:
				dp[r] = arr[l] - arr[r]
			else:
				dp[l] = arr[r] - arr[l]
		l += 1
		r -= 1
	cnt = dp[0]
	for i in range(1, n):
		cnt += max(0, dp[i] - dp[i - 1])
	print(cnt)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	diff = [a[i] - a[n - i - 1] for i in range(n)]
	res = 0
	i = 0
	while i < n:
		if diff[i] < 0:
			j = i
			m = diff[j]
			while j < n and diff[j] < 0:
				m = max(diff[j], m)
				j += 1
			for k in range(i, j):
				diff[k] -= m
			res -= m
			i -= 1
		i += 1
	print(res)


def ppp():
	n = int(input())
	ax = list(map(int, input().split()))
	(low, high, l, r, ctr) = (0, n - 1, 0, 0, 0)
	while low < high:
		dif = abs(ax[low] - ax[high])
		if ax[low] < ax[high]:
			if l <= dif:
				mp = max(dif - l, 0)
				ctr = ctr + mp
			l = dif
			r = 0
		elif ax[low] > ax[high]:
			if r <= dif:
				mp = max(dif - r, 0)
				ctr = ctr + mp
			r = dif
			l = 0
		else:
			l = min(l, r)
			r = min(l, r)
		l = max(l, 0)
		r = max(r, 0)
		low += 1
		high -= 1
	print(ctr)

def Driver():
	for _ in range(int(input())):
		ppp()
Driver()


import random
import math
from collections import defaultdict, Counter, deque, OrderedDict
from functools import lru_cache
import bisect
import heapq
import sys
input = lambda : sys.stdin.readline().strip()

class SegmentTree:

	def __init__(self, arr, func=lambda x, y: x + y, defaultvalue=0):
		self.n = len(arr)
		self.segmentTree = [0] * self.n + arr
		self.func = func
		self.defaultvalue = defaultvalue
		self.buildSegmentTree(arr)

	def buildSegmentTree(self, arr):
		for i in range(self.n - 1, 0, -1):
			self.segmentTree[i] = self.func(self.segmentTree[2 * i], self.segmentTree[2 * i + 1])

	def query(self, l, r):
		l += self.n
		r += self.n
		res = self.defaultvalue
		while l < r:
			if l & 1:
				res = self.func(res, self.segmentTree[l])
				l += 1
			l >>= 1
			if r & 1:
				r -= 1
				res = self.func(res, self.segmentTree[r])
			r >>= 1
		return res

	def update(self, i, value):
		i += self.n
		self.segmentTree[i] = value
		while i > 1:
			i >>= 1
			self.segmentTree[i] = self.func(self.segmentTree[2 * i], self.segmentTree[2 * i + 1])

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = list(range(n))

	def find(self, x):
		if self.parents[x] == x:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			self.parents[x] = y
dire = [0, 1, 0, -1, 0]

def is_prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def case(t):
	print('Case #{}:'.format(t), end=' ')
RANDOM = random.randrange(2 ** 62)

def Wrapper(x):
	return x ^ RANDOM

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	if n % 2 == 1:
		n -= 1
		arr.pop(n // 2)
	add = [0] * n
	(l, r) = (0, n - 1)
	while l < r:
		if arr[l] > arr[r]:
			add[r] += arr[l] - arr[r]
		else:
			add[l] += arr[r] - arr[l]
		l += 1
		r -= 1
	ans = 0
	last = 0
	for i in range(n):
		if add[i] > last:
			ans += add[i] - last
		last = add[i]
	print(ans)
for t in range(int(input())):
	solve()


n = int(input())

def move(arr):
	P = []
	T = []
	for i in range(len(arr) // 2):
		P.append(0)
		T.append(arr[i] - arr[len(arr) - i - 1])
	difs = [x - y for (x, y) in zip(P, T)]
	return sum((abs(x - y) for (x, y) in zip(difs + [0], [0] + difs))) // 2
for i in range(n):
	l = int(input())
	arr = list(map(int, input().split()))
	print(move(arr))


n12 = int(input())
for k12 in range(n12):
	n = int(input())
	l = list(map(int, input().split()))[:n]
	a = []
	for i in range(n // 2):
		x = l[i] - l[n - i - 1]
		a.append(x)
	max = 0
	sum = 0
	val = a[0]
	for i in range(n // 2 - 1):
		if a[i] >= 0:
			if a[i + 1] > 0:
				if val > a[i + 1]:
					sum += val - a[i + 1]
					val = a[i + 1]
				else:
					val = a[i + 1]
			else:
				sum += a[i]
				val = a[i + 1]
		elif a[i + 1] >= 0:
			sum -= a[i]
			val = a[i + 1]
		elif val < a[i + 1]:
			sum += a[i + 1] - val
			val = a[i + 1]
		else:
			val = a[i + 1]
	if val >= 0:
		print(sum + val)
	else:
		print(sum - val)


def print_minimum_moves(arr):
	minimum_moves = 0
	left_index = 0
	right_index = len(arr) - 1
	left_free_moves = 0
	right_free_moves = 0
	while left_index < right_index:
		left_value = arr[left_index]
		right_value = arr[right_index]
		if left_value < right_value:
			needed_moves = right_value - left_value
			discounted_needed_moves = max(0, needed_moves - left_free_moves)
			minimum_moves += discounted_needed_moves
			left_free_moves = needed_moves
			right_free_moves = 0
		elif left_value > right_value:
			needed_moves = left_value - right_value
			discounted_needed_moves = max(0, needed_moves - right_free_moves)
			minimum_moves += discounted_needed_moves
			right_free_moves = needed_moves
			left_free_moves = 0
		else:
			left_free_moves = 0
			right_free_moves = 0
		left_index += 1
		right_index -= 1
	print(minimum_moves)
t = int(input())
for i in range(t):
	n = int(input())
	arr = input().split()
	arr = [int(c) for c in arr]
	print_minimum_moves(arr)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = [a[i] - a[n - i - 1] for i in range(n // 2)]
	(ans, curr) = (0, 0)
	for i in b:
		if i > 0:
			if curr >= 0:
				ans += max(0, i - curr)
			else:
				ans += i
		elif i < 0:
			if curr <= 0:
				ans += max(0, curr - i)
			else:
				ans += -i
		curr = i
	print(ans)


from math import *
from collections import *
import io, os
import sys
MOD = 998244353

def subinp():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def subinp_1():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('op2.txt', 'w')

class Point:

	def __init__(self, x, l1):
		self.x = x
		self.l1 = l1

	def __lt__(self, b):
		return self.l1[self.x] < self.l1[b.x]

	def getval(self):
		return self.x
inp = lambda : int(input())
strin = lambda : input().strip()
strl = lambda : list(input().rstrip('\r\n'))
strlst = lambda : list(map(str, input().split()))
mult = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
lstin = lambda : list(map(int, input().strip().split()))
flush = lambda : stdout.flush()
stdpr = lambda x: stdout.write(str(x))

def panda(n, arr):
	dp = [0] * n
	(i, j) = (0, n - 1)
	while i < j:
		if arr[i] < arr[j]:
			dp[i] += arr[j] - arr[i]
		elif arr[i] > arr[j]:
			dp[j] += arr[i] - arr[j]
		i += 1
		j -= 1
	ans = 0
	res = 0
	for i in dp:
		ans += max(0, i - res)
		res = i
	return ans
t = 1
t = int(input())
for _ in range(t):
	n = inp()
	arr = lstin()
	ans = panda(n, arr)
	print(ans)


from sys import stdin
for t in range(int(stdin.readline())):
	n = int(stdin.readline())
	lis = list(map(int, stdin.readline().split()))
	if n % 2 == 0:
		s = n // 2 - 1
		e = n // 2
	else:
		s = n // 2 - 1
		e = n // 2 + 1
	c = 0
	last = ['n', 0, 0]
	while s != -1:
		if lis[s] == lis[e]:
			s -= 1
			e += 1
			last = ['n', 0, 0]
		elif lis[s] > lis[e]:
			if last[0] != 'e':
				c = c + lis[s] - lis[e]
			elif lis[s] - lis[e] > last[2]:
				c = c + lis[s] - lis[e] - last[2]
			last = ['e', e, lis[s] - lis[e]]
			s -= 1
			e += 1
		elif lis[s] < lis[e]:
			if last[0] != 's':
				c = c + lis[e] - lis[s]
			elif lis[e] - lis[s] > last[2]:
				c = c + lis[e] - lis[s] - last[2]
			last = ['s', s, lis[e] - lis[s]]
			s -= 1
			e += 1
	print(c)


from collections import *
from itertools import *
from functools import *
from heapq import *
import sys, math
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	p1 = 0
	p2 = n - 1
	ans = 0
	while True:
		if l[p1] > l[p2]:
			if p2 - p1 < 1:
				break
			crr = l[p1] - l[p2]
			ans += crr
			p1 += 1
			p2 -= 1
			if p2 - p1 < 1:
				break
			while l[p1] >= l[p2]:
				if l[p1] - l[p2] > crr:
					ans += l[p1] - l[p2] - crr
					crr = l[p1] - l[p2]
				else:
					crr = l[p1] - l[p2]
				p1 += 1
				p2 -= 1
				if p2 - p1 < 1:
					break
		else:
			if p2 - p1 < 1:
				break
			crr = l[p2] - l[p1]
			ans += crr
			p1 += 1
			p2 -= 1
			if p2 - p1 < 1:
				break
			while l[p2] >= l[p1]:
				if l[p2] - l[p1] > crr:
					ans += l[p2] - l[p1] - crr
					crr = l[p2] - l[p1]
				else:
					crr = l[p2] - l[p1]
				p1 += 1
				p2 -= 1
				if p2 - p1 < 1:
					break
	print(ans)


t = int(input())

def minops(A):
	res = pre = 0
	for a in A:
		res += max(a - pre, 0)
		pre = a
	return res
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	i = 0
	j = n - 1
	res = 0
	ctr = [0] * n
	while i < j:
		if arr[i] < arr[j]:
			ctr[i] = arr[j] - arr[i]
		elif arr[i] > arr[j]:
			ctr[j] = arr[i] - arr[j]
		i += 1
		j -= 1
	print(minops(ctr))


T = int(input())
for testNum in range(T):
	moves = 0
	excessR = 0
	excessL = 0
	N = int(input())
	nums = list(map(int, input().split(' ')))
	for i in range(int(N / 2)):
		valR = nums[i]
		valL = nums[N - 1 - i]
		dif = abs(valR - valL)
		if dif == 0:
			moves += excessR + excessL
			excessL = 0
			excessR = 0
		elif valR > valL:
			if excessR > 0:
				if excessR > dif:
					moves += excessR - dif
				excessR = dif
			else:
				moves += excessL
				excessL = 0
				excessR = dif
		elif excessL > 0:
			if excessL > dif:
				moves += excessL - dif
			excessL = dif
		else:
			moves += excessR
			excessR = 0
			excessL = dif
	print(moves + excessR + excessL)


import sys, math, heapq, bisect, random, itertools
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)
ints = lambda : list(map(int, input().split()))
p = 10 ** 9 + 7
inf = 10 ** 20 + 7
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
for t in range(int(input())):
	n = int(input())
	a = ints()
	(l, r) = (0, n - 1)
	(ml, mr) = (0, 0)
	ans = 0
	while l < r:
		if a[l] == a[r]:
			ml = 0
			mr = 0
			l += 1
			r -= 1
		else:
			if a[l] < a[r]:
				if a[r] - a[l] - ml > 0:
					ans += a[r] - a[l] - ml
				ml = a[r] - a[l]
				mr = 0
			else:
				if a[l] - a[r] - mr > 0:
					ans += a[l] - a[r] - mr
				mr = a[l] - a[r]
				ml = 0
			l += 1
			r -= 1
	print(ans)