Little Leon lives in the forest. He has recently noticed that some trees near his favourite path are withering, while the other ones are overhydrated so he decided to learn how to control the level of the soil moisture to save the trees.

There are $n$ trees growing near the path, the current levels of moisture of each tree are denoted by the array $a_1, a_2, \dots, a_n$. Leon has learned three abilities which will help him to dry and water the soil.

Choose a position $i$ and decrease the level of moisture of the trees $1, 2, \dots, i$ by $1$.

Choose a position $i$ and decrease the level of moisture of the trees $i, i + 1, \dots, n$ by $1$.

Increase the level of moisture of all trees by $1$.

Leon wants to know the minimum number of actions he needs to perform to make the moisture of each tree equal to $0$.


-----Input-----

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

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 200000$).

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

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $200000$.


-----Output-----

For each test case output a single integer — the minimum number of actions. It can be shown that the answer exists.


-----Examples-----

Input
4
3
-2 -2 -2
3
10 4 7
4
4 -4 4 -4
5
1 -2 3 -4 5
Output
2
13
36
33


-----Note-----

In the first test case it's enough to apply the operation of adding $1$ to the whole array $2$ times.

In the second test case you can apply the operation of decreasing $4$ times on the prefix of length $3$ and get an array $6, 0, 3$.

After that apply the operation of decreasing $6$ times on the prefix of length $1$ and $3$ times on the suffix of length $1$. In total, the number of actions will be $4 + 6 + 3 = 13$. It can be shown that it's impossible to perform less actions to get the required array, so the answer is $13$.

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

Data structures

Constructive algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
import sys

def solution(arr_):
	diff = [arr_[0] for i in range(len(arr_))]
	for i in range(1, len(arr_)):
		diff[i] = arr_[i] - arr_[i - 1]
	res = 0
	for n in diff[1:]:
		if n < 0:
			res -= n
			diff[0] += n
		else:
			res += n
	res += abs(diff[0])
	return res
case_num = int(sys.stdin.readline().strip())
for case_idx in range(case_num):
	sys.stdin.readline().strip()
	arr_ = list(map(int, sys.stdin.readline().strip().split()))
	print(solution(arr_))


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	curr = arr[0]
	ans = 0
	for i in range(n - 1):
		if curr <= arr[i + 1]:
			curr = arr[i + 1]
		else:
			ans += curr - arr[i + 1]
			curr = arr[i + 1]
	f = arr[0] - ans
	b = arr[-1]
	if f < 0:
		ans += abs(f)
		b += abs(f)
	return b + ans
for _ in range(int(input())):
	print(solve())


import sys
input = sys.stdin.readline

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

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

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

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

def solution(n, a):
	diff = []
	for i in range(n - 1):
		diff.append(a[i + 1] - a[i])
	left_dec = 0
	right_dec = 0
	for d in diff:
		if d > 0:
			right_dec += d
		elif d < 0:
			left_dec += -d
	level_posn = a[0] - left_dec
	return left_dec + right_dec + abs(level_posn)
tests = inp()
for test in range(tests):
	n = inp()
	a = inlt()
	print(solution(n, a))


import sys

def II():
	return int(sys.stdin.readline())

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

def SI():
	return sys.stdin.readline().rstrip()

def MIN_INT():
	return -1 * sys.maxsize

def MAX_INT():
	return sys.maxsize

def prefSum(arr, n):
	P = [0] * (n + 1)
	for k in range(1, n + 1):
		P[k] = P[k - 1] + arr[k - 1]
	return P

def GCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return abs(x)

def solve():
	n = II()
	a = LI()
	prefix = a[0]
	suffix = 0
	ans = 0
	for i in range(1, n):
		a[i] -= suffix
		if a[i] <= prefix:
			ans += prefix - a[i]
			prefix = a[i]
		else:
			suffix += a[i] - prefix
			ans += a[i] - prefix
	ans += abs(prefix)
	return ans

def main():
	t = II()
	for _ in range(t):
		print(solve())
main()


T = int(input())
q = []
for i in range(T):
	n = int(input())
	data = [int(i) for i in input().split()]
	q.append((n, data))

def solve(n, data):
	ans = 0
	for i in range(1, n):
		if data[i - 1] > data[i]:
			ans += data[i - 1] - data[i]
			data[0] -= data[i - 1] - data[i]
	ans += abs(data[0])
	ans += data[n - 1] - data[0]
	print(ans)
for (n, data) in q:
	solve(n, data)


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	a = list(map(int, inp().split()))
	d = [0] * n
	c = 0
	d[0] = a[0]
	for i in range(1, n):
		d[i] = a[i] - a[i - 1]
		if d[i] < 0:
			c -= d[i]
			d[0] += d[i]
		else:
			c += d[i]
	print(c + abs(d[0]))

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


def help(A, n):
	curr = A[0]
	ops = 0
	change = 0
	for i in range(1, n):
		A[i] = A[i] - change
		if A[i] <= curr:
			ops += curr - A[i]
			curr = A[i]
			continue
		else:
			change += A[i] - curr
			A[i] = curr
			continue
	ops += abs(curr)
	ops += change
	return ops
t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	print(help(A, n))


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	nums = list(map(int, sys.stdin.readline().strip().split()))
	d = [0] * n
	for i in range(1, n):
		d[i] = nums[i] - nums[i - 1]
	res = 0
	d[0] = nums[0]
	for i in range(1, n):
		if d[i] > 0:
			res += d[i]
		else:
			res -= d[i]
			d[0] += d[i]
	print(res + abs(d[0]))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	prefix = suffix = 0
	for i in range(n - 1):
		if (d := (a[i] - a[i + 1])) > 0:
			prefix += d
		else:
			suffix -= d
	print(abs(a[0] - prefix) + prefix + suffix)


def solve():
	n = int(input())
	a = [int(x) for x in input().split()]
	init_sum = sum(a)
	ans = 0
	diff = 0
	for i in range(1, n):
		if a[i] > a[i - 1]:
			d = a[i] - a[i - 1]
			ans += d
			diff += (n - i) * d
		else:
			d = a[i - 1] - a[i]
			ans += d
			diff += i * d
	final_sum = init_sum - diff
	fin = final_sum // n
	ans += fin if fin >= 0 else -fin
	print(ans)
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	k = 0
	for i in range(1, n):
		z = l[i] - l[i - 1]
		if z >= 0:
			k += z
	m = l[-1] - k
	mcd = abs(l[0] - m)
	ans = k + abs(m) + mcd
	print(ans)


def help_the_trees(l: list):
	result = 0
	temp = 0
	last = l[-1]
	for index in range(len(l) - 1):
		if l[index] > l[index + 1]:
			dif = l[index] - l[index + 1]
			result += dif
		elif l[index] < l[index + 1]:
			dif = l[index + 1] - l[index]
			result += dif
			temp += dif
	return result + abs(last - temp)
n = int(input())
for i in range(n):
	garbale = input()
	l = list(map(int, input().split()))
	print(help_the_trees(l))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	start = a[0]
	positive = negative = 0
	for i in range(1, n):
		d = a[i] - a[i - 1]
		if d > 0:
			positive += d
		else:
			negative += d
	answer = positive + abs(negative) + abs(start + negative)
	print(answer)


for line in [*open(0)][2::2]:
	tot = 0
	list = line.split(' ')
	list2 = [0] + list
	minv = int(list[0])
	for val in range(len(list) - 1):
		diff = int(list2[val + 1]) - int(list[val + 1])
		if diff >= 0:
			tot += diff
			minv -= diff
	print(tot - minv + abs(minv) + int(list[len(list) - 1]))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	comp = a[0]
	curr = a[0]
	tot = 0
	for a_i in a[1:]:
		diff = a_i - curr
		tot += abs(diff)
		if diff < 0:
			comp += diff
		curr = a_i
	tot += abs(comp)
	print(tot)


def testcase():
	n = int(input())
	a = list(map(int, input().split()))
	assert n == len(a)
	moves = 0
	offset = 0
	base = a[0]
	for i in range(n):
		h = offset + a[i]
		if h == base:
			continue
		if h < base:
			moves += base - h
			base = h
		else:
			offset -= h - base
			moves += h - base
	print(moves + abs(base))
t = int(input())
for i in range(t):
	testcase()


def ck(n, lis):
	dv = 0
	la = lis[0]
	val = 0
	for i in range(1, n):
		ke = lis[i] + dv
		if la > ke:
			val += abs(ke - la)
			la = ke
		else:
			dv += la - ke
			val += abs(la - ke)
	return abs(la) + val
for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	if n == 1:
		print(abs(lis[0]))
	else:
		print(ck(n, lis))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(abs(a[0]))
		continue
	p = 0
	for i in range(n - 1):
		if a[i] > a[i + 1]:
			p += a[i] - a[i + 1]
	if a[0] - p < 0:
		a[-1] += p - a[0]
		p += p - a[0]
	p += a[-1]
	print(p)


for test_case in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	d = 0
	for i in range(n - 1):
		x = l[i] - l[i + 1]
		if x > 0:
			ans += x
		else:
			ans += -x
			d += -x
	d = l[-1] - d
	if d < 0:
		d = -1 * d
	print(ans + d)


def solve():
	n = int(input())
	lis = list(map(int, input().split()))
	ans = 0
	diff = 0
	(ref, diff) = (lis[0], lis[0])
	for i in range(1, n):
		diff = lis[i] - lis[i - 1]
		ans += abs(diff)
		if diff < 0:
			ref += diff
	print(ans + abs(ref))
for _ in range(int(input())):
	solve()


for i in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	ans = am = 0
	for x in range(n - 1):
		cnt = ls[x] - ls[x + 1]
		if cnt > 0:
			ans += cnt
		else:
			ans -= cnt
			am -= cnt
	print(ans + abs(ls[-1] - am))


import math
import sys
import threading
input = sys.stdin.readline
from collections import defaultdict as dd
from collections import deque

def helper(nd):
	vis[nd] = 1
	here = 1
	for ng in gr[nd]:
		if vis[ng] == 0:
			here += helper(ng)
	tot[nd] = here
	return here

def helper1(nd, par):
	ch = []
	for ng in gr[nd]:
		if ng != par:
			ch.append(ng)
	if len(ch) == 0:
		return 0
	if len(ch) == 1:
		return tot[nd] - 2
	return max(tot[ch[1]] - 1 + helper1(ch[0], nd), tot[ch[0]] - 1 + helper1(ch[1], nd))

def shouvik():
	T = int(input())
	for _ in range(T):
		n = int(input())
		arr = list(map(int, input().split()))
		ans = 0
		for i in range(1, n):
			arr[i] -= ans
			if arr[i - 1] < arr[i]:
				ans += arr[i] - arr[i - 1]
				arr[i] = arr[i - 1]
		here = 0
		for i in range(n - 2, -1, -1):
			delta = arr[i] - here - arr[i + 1]
			here += delta
			arr[i] = arr[i + 1]
		ans += here
		print(ans + abs(arr[0]))
shouvik()


import os, sys
isLocal = os.environ.get('USER', '') == 'xueenpeng'
if isLocal:
	sys.stdin = open('./file/input.txt', 'r')
	pass

def cal(n, arr):
	diffArray = [0]
	for index in range(1, n):
		last = arr[index - 1]
		cur = arr[index]
		diffArray.append(cur - last)
	ans = 0
	for (index, diff) in enumerate(diffArray):
		if diff == 0:
			continue
		elif diff > 0:
			diffArray[index] = 0
			ans += diff
		else:
			diffArray[0] += diff
			diffArray[index] -= diff
			ans -= diff
	ans += abs(arr[0] + diffArray[0])
	return ans

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().split(' ')))
		print(cal(n, arr))
main()


def main():
	n = int(input())
	a = list(map(int, input().split()))
	p = 0
	ans = 0
	for i in range(n - 1):
		if a[i] < a[i + 1]:
			d = a[i + 1] - a[i]
			p += d
			ans += d
		else:
			d = a[i] - a[i + 1]
			ans += d
	v = a[-1] - p
	ans += abs(v)
	print(ans)
for _ in range(int(input())):
	main()


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	for j in range(n - 1):
		count += abs(a[j] - a[j + 1])
		if a[j] > a[j + 1]:
			a[0] += a[j + 1] - a[j]
	count += abs(a[0])
	print(count)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	f = 0
	for j in range(1, n):
		f += max(0, a[j - 1] - a[j])
	a[0] -= f
	f += abs(a[-1] - a[0]) + abs(a[0])
	print(f)


for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	f = 0
	n = 0
	for i in range(a - 1):
		res = b[i] - b[i + 1]
		if res > 0:
			f += res
		else:
			f += abs(res)
			n += abs(res)
	result = b[-1] - n
	if result > 0:
		print(f + result)
	else:
		print(f + abs(result))


for k in range(int(input())):
	num = int(input())
	b = list(map(int, input().split()))
	f = 0
	for j in range(1, num):
		f += max(0, b[j - 1] - b[j])
	b[0] -= f
	f += abs(b[-1] - b[0]) + abs(b[0])
	print(f)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	s = s.split()
	a = [int(x) for x in s]
	out = 0
	correction = a[0]
	for i in range(1, n):
		diff = a[i] - a[i - 1]
		if diff < 0:
			out -= diff
			correction += diff
		elif diff > 0:
			out += diff
	out += abs(correction)
	print(out)


def saveTrees():
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	first = arr[0]
	for i in range(n - 1):
		ans += abs(arr[i] - arr[i + 1])
		if arr[i] > arr[i + 1]:
			first += arr[i + 1] - arr[i]
	print(ans + abs(first))
t = int(input())
for i in range(t):
	saveTrees()


x = int(input())

def cal(n, p):
	if n == 1:
		return abs(p[0])
	ans = 0
	carry = 0
	for i in range(1, n):
		if p[i] < p[i - 1]:
			ans += p[i - 1] - p[i]
		else:
			ans += p[i] - p[i - 1]
			carry += p[i] - p[i - 1]
	return ans + abs(carry - p[-1])
for jj in range(x):
	n = int(input())
	p = [int(i) for i in input().split(' ')]
	print(cal(n, p))


import random
O = random.randint(10, 10 ** 7)

def main():
	N = int(input())
	for _ in range(N):
		n = int(input())
		arr = list(map(int, input().split()))
		cur = arr[0]
		ans = 0
		d = 0
		for i in range(1, len(arr)):
			b = arr[i] - d
			if cur > b:
				ans += cur - b
				cur = b
			else:
				d += b - cur
				ans += b - cur
		ans += abs(cur)
		print(ans)

def init():
	import os
	import sys
	sys.setrecursionlimit(2 * 10 ** 6)
	if 'CP_LOCAL_ENV' in os.environ:
		sys.stdin = open('cf_test_c.txt')
init()
main()


from collections import Counter, deque
from collections import OrderedDict
import math
from random import randint
from bisect import bisect, bisect_left
import sys
import re
MOD = 10 ** 9 + 7
MAX = -sys.maxsize
MIN = sys.maxsize

class get:

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

	def str():
		return input().split()

	def float():
		return list(map(float, input().split()))

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

def sqrt(x):
	return int(math.sqrt(x)) + 1

def gcd(*args):
	result = args[0]
	for item in args:
		result = math.gcd(result, item)
	return result

def LCM(a, b):
	return a * b // math.gcd(a, b)

def isPrime(n):
	if n == 1:
		return False
	for i in range(2, sqrt(n)):
		if n % i == 0:
			return False
	return True

def solve():
	n = int(input())
	a = get.int()
	if n == 1:
		print(abs(a[0]))
		return
	res = 0
	for i in range(n - 2, -1, -1):
		a[i] -= res
		if a[i] > a[i + 1]:
			res += a[i] - a[i + 1]
			a[i] = a[i + 1]
	if a[0] < 0:
		print(res + 2 * abs(a[0]) + a[-1])
	else:
		print(res + a[-1])
t = int(input())
for tt in range(t):
	solve()


T = int(input())
for Ti in range(T):
	n = int(input().strip())
	l = [int(i) for i in input().split(' ')]
	sum = 0
	ans = 0
	for i in range(1, len(l)):
		dif = l[i] - l[i - 1]
		ans += abs(dif)
		if dif < 0:
			sum += dif
	ans += abs(l[0] + sum)
	print(ans)


def solve():
	n = int(input())
	a = [int(x) for x in input().split()]
	ops = 0
	maxi = a[0]
	for i in range(1, n):
		a[i] -= ops
		if a[i] <= maxi:
			maxi = a[i]
		else:
			ops += a[i] - maxi
		a[i] = maxi
	maxi = a[n - 1]
	ans = ops
	ops = 0
	for i in range(n - 2, -1, -1):
		a[i] -= ops
		if a[i] > maxi:
			ops += a[i] - maxi
		a[i] = maxi
	ans += ops
	ans += abs(a[0])
	print(ans)
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	steps = 0
	for x in range(n - 1):
		steps += abs(arr[x] - arr[x + 1])
		if arr[x] > arr[x + 1]:
			arr[0] -= abs(arr[x + 1] - arr[x])
	steps += abs(arr[0])
	print(steps)


for time in range(int(input())):
	n = int(input())
	nums = [int(a) for a in input().split()]
	s = 0
	k = nums[0]
	for j in range(n - 1):
		l = abs(nums[j] - nums[j + 1])
		s += l
		if nums[j] > nums[j + 1]:
			k -= l
	print(s + abs(k))


t = int(input())
for i in range(t):
	l = int(input())
	arr = [int(i) for i in input().split(' ')]
	ans = 0
	rem = arr[0]
	for i in range(l - 1):
		ans += abs(arr[i + 1] - arr[i])
		if arr[i + 1] < arr[i]:
			rem += arr[i + 1] - arr[i]
	ans += abs(rem)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	k = arr[0]
	for i in range(n - 1):
		dif = abs(arr[i] - arr[i + 1])
		ans += dif
		if arr[i] > arr[i + 1]:
			k = k - dif
	print(ans + abs(k))


t = int(input())
while t:
	t -= 1
	n = int(input())
	l = [int(x) for x in input().split()]
	diff = [l[i] - l[i + 1] for i in range(n - 1)]
	ans = 0
	for d in diff:
		ans += abs(d)
	tmp = l[0]
	for d in diff:
		if d > 0:
			tmp -= d
	ans += abs(tmp)
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	substracted = 0
	a = list(map(int, input().split()))
	diff = [a[i] - a[i + 1] for i in range(n - 1)]
	substracted = sum([i for i in diff if i < 0])
	steps = sum([abs(i) for i in diff])
	steps += abs(a[n - 1] + substracted)
	print(steps)


for i in range(int(input())):
	p = int(input())
	q = list(map(int, input().split()))
	r = 0
	for j in range(1, p):
		r += max(0, q[j - 1] - q[j])
	q[0] -= r
	r += abs(q[-1] - q[0]) + abs(q[0])
	print(r)


for i in range(int(input())):
	lenn = int(input())
	list1 = list(map(int, input().split()))
	ans = 0
	minn = min(list1)
	imp = list1[0]
	imp1 = list1[-1]
	for i in range(lenn - 1):
		if list1[i] > list1[i + 1]:
			ans += list1[i] - list1[i + 1]
			imp -= list1[i] - list1[i + 1]
	if imp < 0:
		ans += abs(imp)
		imp1 += abs(imp)
	ans += imp1
	print(ans)


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


for p in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	minv = 10 ** 10
	oper = 0
	t = 0
	curv = a[0]
	for i in range(1, n):
		if a[i] - t <= curv:
			oper += curv - (a[i] - t)
			curv = a[i] - t
		else:
			oper += a[i] - t - curv
			t = t + (a[i] - t - curv)
	print(abs(curv) + oper)


t = int(input())
for i in range(0, t):
	totalsteps = 0
	trees = int(input())
	value = input()
	value = value.split(' ')
	value = [int(k) for k in value]
	finaldistance = value[trees - 1]
	for j in range(0, trees - 1):
		steps = 0
		if value[j] == value[j + 1]:
			continue
		elif value[j] < value[j + 1]:
			steps = value[j + 1] - value[j]
			finaldistance -= steps
		elif value[j] > value[j + 1]:
			steps = value[j] - value[j + 1]
		totalsteps += steps
	totalsteps += abs(finaldistance)
	print(totalsteps)


t = int(input())
while t > 0:
	n = int(input())
	moves = 0
	lst = list(map(int, input().strip().split()))
	for i in range(len(lst) - 1):
		moves = moves + abs(lst[i + 1] - lst[i])
		if lst[i] > lst[i + 1]:
			lst[0] = lst[0] + lst[i + 1] - lst[i]
	moves = moves + abs(lst[0])
	t = t - 1
	print(moves)


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	nums = [0] + nums
	d = [0] * (n + 1)
	for i in range(1, n + 1):
		if i == 1:
			d[i] = nums[i]
		else:
			d[i] = nums[i] - nums[i - 1]
	cnt = 0
	for i in range(2, n + 1):
		if d[i] > 0:
			cnt += d[i]
		elif d[i] < 0:
			cnt += -d[i]
			d[1] += d[i]
	if d[1] < 0:
		cnt += -d[1]
	elif d[1] > 0:
		cnt += d[1]
	print(cnt)


for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	ans = 0
	cur = a[0]
	for i in range(1, n):
		ans += abs(a[i] - a[i - 1])
		if a[i - 1] > a[i]:
			cur -= a[i - 1] - a[i]
	print(ans + abs(cur))


for _ in range(int(input())):
	s = int(input())
	z = list(map(int, input().split()))
	total = 0
	right = 0
	for i in range(1, len(z)):
		z[i] -= right
		if z[i] <= z[i - 1]:
			total += abs(z[i] - z[i - 1])
		else:
			total += abs(z[i] - z[i - 1])
			right += abs(z[i] - z[i - 1])
			z[i] = z[i - 1]
	print(total + abs(z[-1]))


for _ in range(int(input())):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = []
	for a in arr1[::-1]:
		arr2.append(a)

	def func(arr):
		left = arr[0]
		sub = 0
		ans = 0
		for a in arr:
			val = a + sub
			if val > left:
				sub -= abs(val - left)
				ans += abs(val - left)
			elif val < left:
				ans += abs(left - val)
				left = val
		ans += abs(left)
		return ans
	print(min(func(arr1), func(arr2)))


x = int(input())
for testCases in range(x):
	n = int(input())
	answer = 0
	array = input().split(' ')
	for i in range(len(array)):
		array[i] = int(array[i])
	currH = array[0]
	for i in range(len(array) - 1):
		answer += abs(array[i] - array[i + 1])
		if array[i] > array[i + 1]:
			currH += array[i + 1] - array[i]
	print(answer + abs(currH))


t = int(input())
for i in range(t):
	nt = int(input())
	lst = list(map(int, input().split()))
	act = 0
	for i in range(nt - 1):
		act += abs(lst[i] - lst[i + 1])
		if lst[i + 1] - lst[i] < 0:
			lst[0] -= abs(lst[i + 1] - lst[i])
	act += abs(lst[0])
	print(act)


def func(n, a):
	b = [0 for i in range(n)]
	ans = 0
	b[-1] = a[-1]
	for i in range(n - 1, 0, -1):
		if a[i - 1] > a[i]:
			ans += a[i - 1] - a[i]
			b[i - 1] = b[i]
		else:
			b[i - 1] = a[i - 1] - ans
	ans += abs(b[0])
	for i in range(n - 1):
		if b[i] != b[i + 1]:
			ans += b[i + 1] - b[i]
	return ans
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(func(n, a))


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


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


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	maxi = a[0]
	ops = 0
	for i in range(1, n):
		a[i] -= ops
		if a[i] <= maxi:
			maxi = a[i]
		else:
			ops += a[i] - maxi
		a[i] = maxi
	maxi = a[-1]
	ans = ops
	ops = 0
	for i in range(n - 2, -1, -1):
		a[i] -= ops
		if a[i] > maxi:
			ops += a[i] - maxi
		a[i] = maxi
	ans += ops
	ans += abs(a[0])
	print(ans)


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


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(abs(l[0]))
		continue
	ans = 0
	x = 0
	t = l[0]
	for i in range(n - 1):
		c = x + l[i + 1]
		ans += abs(l[i + 1] - l[i])
		if l[i] <= l[i + 1]:
			x -= l[i + 1] - l[i]
		else:
			t = min(t, l[i + 1] + x)
	ans += abs(t)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	sum = 0
	mini = arr[0]
	extra = 0
	for i in range(n - 1):
		mini = min(mini, arr[i + 1] - extra)
		if arr[i] >= arr[i + 1]:
			sum += arr[i] - arr[i + 1]
		else:
			sum += arr[i + 1] - arr[i]
			extra += arr[i + 1] - arr[i]
	print(int(sum + abs(mini)))


import sys
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, sys.stdin.readline().split()))
	sub = 0
	last = arr[-1]
	res = 0
	for i in range(n - 2, -1, -1):
		if arr[i] - sub > last:
			diff = last - (arr[i] - sub)
			res += abs(diff)
			sub += abs(diff)
		else:
			last = arr[i] - sub
		arr[i] = last
	if arr[0] < 0:
		res += abs(arr[0])
		arr[-1] += abs(arr[0])
	print(res + arr[-1])


t = int(input())
while t:
	n = int(input())
	a = [0] + list(map(int, input().split(' '))) + [0]
	b = [0] * (n + 2)
	for i in range(1, n + 1):
		b[i] = a[i] - a[i - 1]
	b[n + 1] = -a[n]
	(x, y) = (0, 0)
	for i in range(2, n + 1):
		if b[i] > 0:
			x += b[i]
		else:
			y -= b[i]
	b[1] -= x
	b[-1] += y
	ans = x + y + abs(b[1] - b[n + 1]) // 2
	print(ans)
	t -= 1


def num():
	c = int(input())
	return c

def stri():
	c = str(input())
	return c

def vector():
	c = list(map(int, input().split()))
	return c

def strvector():
	c = list(map(str, input().split()))
	return c
import math

def isprime(num):
	a = 2
	while a <= math.sqrt(num):
		if num % a < 1:
			return False
		a = a + 1
	return num > 1
t = num()
while t > 0:
	t -= 1
	n = num()
	arr = vector()
	cnt = 0
	x = 0
	h = [0] * n
	for i in range(n - 2, -1, -1):
		if arr[i] - x > arr[i + 1] - x:
			x += arr[i] - arr[i + 1]
			h[i] = x
			cnt += arr[i] - arr[i + 1]
		else:
			h[i] = x
	y = [0] * n
	x = 0
	for i in range(1, n):
		if arr[i] - x > arr[i - 1] - x:
			x += arr[i] - arr[i - 1]
			y[i] = x
			cnt += arr[i] - arr[i - 1]
		else:
			y[i] = x
	print(cnt + abs(arr[0] - h[0] - y[0]))


for q in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	lis = arr.copy()
	minus = 0
	ans = 0
	for i in range(1, n):
		lis[i] = lis[i] - minus
		if lis[i] > lis[i - 1]:
			ans += lis[i] - lis[i - 1]
			minus += lis[i] - lis[i - 1]
			lis[i] = lis[i - 1]
	for i in range(n - 1):
		ans += lis[i] - lis[i + 1]
	ans += abs(lis[-1])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(pos, neg) = (0, 0)
	ans = 0
	(positive, negative) = ([0] * n, [0] * n)
	for i in range(1, n):
		if arr[i] > arr[i - 1]:
			positive[i] += arr[i] - arr[i - 1]
		else:
			negative[i - 1] += arr[i - 1] - arr[i]
			neg += negative[i - 1]
	for i in range(len(arr)):
		ans += positive[i] + negative[i]
		pos += positive[i]
		arr[i] -= pos + neg
		neg -= negative[i]
	print(ans + abs(arr[0]))