In this challenge, you will be given an array $\mbox{B}$ and must determine an array $\mbox{A}$.  There is a special rule:  For all $\boldsymbol{i}$, $A[i]\leq B[i]$.  That is, $A[i]$ can be any number you choose such that $1\leq A[i]\leq B[i]$.  Your task is to select a series of $A[i]$ given $B[i]$ such that the sum of the absolute difference of consecutive pairs of $\mbox{A}$ is maximized.  This will be the array's cost, and will be represented by the variable $\mbox{S}$ below. 

The equation can be written:

$S=\sum_{i=2}^{N}|A[i]-A[i-1]|$

For example, if the array $B=[1,2,3]$, we know that $1\leq A[1]\leq1$, $1\leq A[2]\leq2$, and $1\leq A[3]\leq3$.  Arrays meeting those guidelines are:

[1,1,1], [1,1,2], [1,1,3]
[1,2,1], [1,2,2], [1,2,3]

Our calculations for the arrays are as follows:

|1-1| + |1-1| = 0	|1-1| + |2-1| = 1	|1-1| + |3-1| = 2
|2-1| + |1-2| = 2	|2-1| + |2-2| = 1	|2-1| + |3-2| = 2

The maximum value obtained is $2$.

Function Description

Complete the cost function in the editor below.  It should return the maximum value that can be obtained.  

cost has the following parameter(s):  

B: an array of integers  

Input Format

The first line contains the integer $\boldsymbol{\boldsymbol{t}}$, the number of test cases. 

Each of the next $\boldsymbol{\boldsymbol{t}}$ pairs of lines is a test case where: 

- The first line contains an integer $n$, the length of $\mbox{B}$ 

- The next line contains $n$ space-separated integers $B[i]$  

Constraints

$1\leq t\leq20$ 
$1<n\leq10^5$
$1\leq B[i]\leq100$

Output Format

For each test case, print the maximum sum on a separate line.   

Sample Input
1
5
10 1 10 1 10

Sample Output
36

Explanation

The maximum sum occurs when A[1]=A[3]=A[5]=10 and A[2]=A[4]=1.  That is $|1-10|+|10-1|+|1-10|+|10-1|=36$.

Source: hackerrank | Difficulty: MEDIUM
Tags: Dynamic programming


Solutions:
def cost(B):
	(c0, c1) = (0, 0)
	for i in range(1, len(B)):
		(c0, c1) = (max(c0, c1 + B[i - 1] - 1), max(c0 + B[i] - 1, c1 + abs(B[i] - B[i - 1])))
	return max(c0, c1)
T = int(input())
for _ in range(T):
	N = int(input())
	B = [int(_) for _ in input().strip().split()]
	print(cost(B))


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


cases = int(input())
for i in range(cases):
	Nvals = int(input())
	vals = [int(x) for x in input().strip().split()]
	dp0 = [0] * Nvals
	dp1 = [0] * Nvals
	dp0[0] = 0
	dp1[0] = 0
	for j in range(1, Nvals):
		dp0[j] = max(abs(1 - 1) + dp0[j - 1], abs(1 - vals[j - 1]) + dp1[j - 1])
		dp1[j] = max(abs(vals[j] - 1) + dp0[j - 1], abs(vals[j] - vals[j - 1]) + dp1[j - 1])
	print(max(dp1[Nvals - 1], dp0[Nvals - 1]))


import sys
T = int(sys.stdin.readline().strip())
for t in range(T):
	sys.stdin.readline()
	B = list(map(lambda x: int(x.strip()), sys.stdin.readline().split()))
	A = [[0, 0] for i in range(len(B))]
	for i in range(0, len(B) - 1):
		A[i + 1][0] = max(A[i][0], A[i][1] + abs(B[i] - 1))
		A[i + 1][1] = max(A[i][0] + abs(B[i + 1] - 1), A[i][1] + abs(B[i] - B[i + 1]))
	print(max(A[-1]))


T = int(input())
B = []

def buildArray(M, N):
	M[0][0] = 0
	M[0][1] = 0
	for i in range(1, N):
		M[i][0] = max(M[i - 1][0], abs(B[i - 1] - 1) + M[i - 1][1])
		M[i][1] = max(abs(B[i] - 1) + M[i - 1][0], abs(B[i] - B[i - 1]) + M[i - 1][1])
for i in range(T):
	N = int(input())
	B = list(map(int, input().split()))
	M = [[-1 for x in range(2)] for x in range(N)]
	buildArray(M, N)
	print(max(M[N - 1][0], M[N - 1][1]))
	M.clear()


T = int(input())
for case in range(T):
	N = int(input())
	B = [int(x) for x in input().split()]
	S_1 = S_2 = 0
	for i in range(1, N):
		tS_1 = max(S_1, S_2 + abs(1 - B[i - 1]))
		tS_2 = max(S_1 + abs(B[i] - 1), S_2 + abs(B[i] - B[i - 1]))
		S_1 = tS_1
		S_2 = tS_2
	print(max(S_1, S_2))


def f(B):
	if len(B) == 1:
		return 0
	dp = [B[0] - 1, max(abs(B[1] - B[0]), B[1] - 1)]
	for i in range(2, len(B)):
		(dp[0], dp[1]) = (max(dp[0], dp[1] + B[i - 1] - 1), max(dp[0] + B[i] - 1, dp[1] + abs(B[i] - B[i - 1])))
	return max(dp)
for _ in range(int(input())):
	input()
	print(f([int(i) for i in input().split()]))


import math
for case in range(int(input())):
	N = int(input())
	B = [int(x) for x in input().split()]
	memo = dict()
	memo[0, 0] = 0
	memo[0, 1] = 0
	for i in range(N - 1):
		memo[i + 1, 0] = max(memo[i, 0], memo[i, 1] + abs(B[i] - 1))
		if i < N - 1:
			memo[i + 1, 1] = max(memo[i, 0] + abs(B[i + 1] - 1), memo[i, 1] + abs(B[i] - B[i + 1]))
		else:
			memo[i + 1, 1] = 0
	print(max(memo[N - 1, 0], memo[N - 1, 1]))


import sys

def cost(b, num):
	cost_sum_one = [0] * num
	cost_sum_two = [0] * num
	for i in range(1, num):
		cost_sum_one[i] = max(cost_sum_one[i - 1], cost_sum_two[i - 1] + b[i - 1] - 1)
		cost_sum_two[i] = max(cost_sum_two[i - 1], cost_sum_one[i - 1] + b[i] - 1)
	return max(cost_sum_one[-1], cost_sum_two[-1])
num_trials = int(sys.stdin.readline())
for trial in range(num_trials):
	n = int(sys.stdin.readline())
	b = list((int(num) for num in sys.stdin.readline().split(' ')))
	print(cost(b, n))


T = int(input())
for t in range(T):
	N = int(input())
	B = [int(c) for c in input().split(' ')]
	dp = [[0, 0] for i in range(N)]
	for i in range(1, N):
		dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + abs(1 - B[i - 1]))
		dp[i][1] = max(dp[i - 1][0] + abs(B[i] - 1), dp[i - 1][1] + abs(B[i] - B[i - 1]))
	print(max(dp[N - 1][0], dp[N - 1][1]))


num_tests = int(input())
while num_tests:
	num_tests -= 1
	arr_size = int(input())
	b_arr = input().split(' ')
	b_arr = [int(x) for x in b_arr]
	max_top_profit = [0]
	max_bottom_profit = [0]
	for i in range(1, arr_size):
		top_profit = max(max_top_profit[i - 1] + abs(b_arr[i] - b_arr[i - 1]), max_bottom_profit[i - 1] + abs(b_arr[i] - 1))
		bottom_profit = max(max_top_profit[i - 1] + abs(1 - b_arr[i - 1]), max_bottom_profit[i - 1])
		max_top_profit.append(top_profit)
		max_bottom_profit.append(bottom_profit)
	print(max(max_top_profit[-1], max_bottom_profit[-1]))


def unrolled(b):
	cache1 = [0] * len(b)
	cacheb = [0] * len(b)
	for i in range(1, len(b)):
		cache1[i] = max(cache1[i - 1] + abs(1 - 1), cacheb[i - 1] + abs(b[i - 1] - 1))
		cacheb[i] = max(cache1[i - 1] + abs(b[i] - 1), cacheb[i - 1] + abs(b[i] - b[i - 1]))
	return max(cache1[-1], cacheb[-1])
for t in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	print(unrolled(b))


T = int(input())
for t in range(T):
	N = int(input())
	dp_table = [[0, 0] for y in range(N)]
	B = [int(b) for b in input().split(' ')]
	for n in range(1, N):
		dp_table[n][0] = max(dp_table[n - 1][0], dp_table[n - 1][1] + abs(1 - B[n - 1]))
		dp_table[n][1] = max(dp_table[n - 1][0] + abs(B[n] - 1), dp_table[n - 1][1] + abs(B[n] - B[n - 1]))
	print(max(dp_table[N - 1][0], dp_table[N - 1][1]))


for _ in range(int(input())):
	length = int(input())
	nums = [int(x) for x in input().split()]
	low = 0
	high = 0
	for (i, v) in enumerate(nums):
		if i > 0:
			l = max(abs(1 - nums[i - 1]) + high, low)
			h = max(abs(v - 1) + low, abs(v - nums[i - 1]) + high)
			low = l
			high = h
	print(max(low, high))


import sys

def findCost(ary):
	l = len(ary)
	if l == 1:
		print(0)
		return
	dp = [[0 for j in range(2)] for i in range(l)]
	dp[0][0] = 0
	dp[0][1] = 0
	for i in range(1, l):
		dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + abs(ary[i - 1] - 1))
		dp[i][1] = max(dp[i - 1][0] + abs(ary[i] - 1), dp[i - 1][1] + abs(ary[i] - ary[i - 1]))
	ans = max(dp[l - 1][0], dp[l - 1][1])
	print(ans)
data = sys.stdin.readlines()
case = int(data[0])
for i in range(case):
	num = data[2 * i + 1]
	line = data[2 * i + 2]
	ary = list(map(int, line.split()))
	findCost(ary)


def main():
	ncases = int(input())
	for _ in range(ncases):
		blen = int(input())
		b = [int(f) for f in input().split()]
		assert blen == len(b)
		print(maxcost(b))

def maxcost(b):
	hicost = locost = 0
	for i in range(1, len(b)):
		(oldhicost, oldlocost) = (hicost, locost)
		hicost = max(abs(b[i] - b[i - 1]) + oldhicost, b[i] - 1 + oldlocost)
		locost = max(b[i - 1] - 1 + oldhicost, oldlocost)
	return max(hicost, locost)
main()


T = int(input())
for case in range(T):
	N = int(input())
	B = list(map(int, input().rstrip().split(' ')))
	dp = [[0] * 2 for _ in range(N)]
	for i in range(N - 1):
		j = N - i - 2
		dp[j][0] = max(abs(B[j] - B[j + 1]) + dp[j + 1][0], abs(B[j] - 1) + dp[j + 1][1])
		dp[j][1] = max(abs(1 - B[j + 1]) + dp[j + 1][0], 1 - 1 + dp[j + 1][1])
	print(max(dp[0]))


cases = int(input())
for _ in range(cases):
	size = int(input())
	B = [int(b) for b in input().split()]
	cost_hi = [0] * size
	cost_lo = [0] * size
	for k in reversed(range(size - 1)):
		cost_hi[k] = max(abs(B[k] - B[k + 1]) + cost_hi[k + 1], abs(B[k] - 1) + cost_lo[k + 1])
		cost_lo[k] = max(abs(1 - B[k + 1]) + cost_hi[k + 1], cost_lo[k + 1])
	print(max(cost_hi[0], cost_lo[0]))


numTrials = int(input())

def max_sum(L):
	(k, m) = (0, 0)
	for i in range(1, len(L)):
		(k, m) = (max(k, m + B[i - 1] - 1), max(k + B[i] - 1, m + abs(B[i] - B[i - 1])))
	return max(k, m)
for i in range(numTrials):
	N = input()
	B = list(map(int, input().split()))
	print(max_sum(B))


t = int(input())
for _ in range(t):
	n = int(input())
	lis = list(map(int, input().split()))
	P = [[0, 0] for x in range(n + 1)]
	for i in range(1, n):
		P[i][0] = max(P[i - 1][1] + abs(lis[i - 1] - 1), P[i - 1][0])
		P[i][1] = max(P[i - 1][0] + abs(lis[i] - 1), P[i - 1][1])
	res = max(P[n - 1][0], P[n - 1][1])
	print(res)


def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		B = [int(x) for x in input().split()]
		dp = [[0, 0]]
		for i in range(1, N):
			dp.append([0, 0])
			dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + abs(B[i - 1] - 1))
			dp[i][1] = max(dp[i - 1][0] + abs(B[i] - 1), dp[i - 1][1] + abs(B[i] - B[i - 1]))
		print(max(dp[-1]))
main()


def sherlock_and_cost(ls):
	dp = [[0 for _ in range(2)] for _ in range(100010)]
	length = len(ls)
	for i in range(2, length + 1):
		dp[i][0] = max(dp[i - 1][1] + abs(1 - ls[i - 2]), dp[i - 1][0])
		dp[i][1] = max(dp[i - 1][1] + abs(ls[i - 1] - ls[i - 2]), dp[i - 1][0] + abs(ls[i - 1] - 1))
	return max(dp[length][0], dp[length][1])
n = int(input())
for _ in range(n):
	k = int(input())
	l = list(map(int, input().split()))
	print(sherlock_and_cost(l))


t = eval(input())
while t > 0:
	t -= 1
	n = eval(input())
	b = list(map(int, input().split()))
	newBottom = 0
	newTop = 0
	for i in range(1, n):
		bottom = newBottom
		top = newTop
		newBottom = top + abs(b[i - 1] - 1)
		if newBottom < bottom:
			newBottom = bottom
		newTop = bottom + abs(b[i] - 1)
		if newTop < top + abs(b[i - 1] - b[i]):
			newTop = top + abs(b[i - 1] - b[i])
	print(newTop if newTop > newBottom else newBottom)


for testcase in range(int(input())):
	N = int(input())
	array = [int(x) for x in input().split()]
	min_last = 0
	max_last = 0
	for i in range(N - 1):
		new_min_last = max(min_last, max_last + array[i + 1] - 1)
		new_max_last = max(max_last, min_last + array[i] - 1)
		(min_last, max_last) = (new_min_last, new_max_last)
	print(max(min_last, max_last))


def cost(N, B):
	C = [[0 for _ in range(2)] for _ in range(N)]
	for i in range(1, N):
		C[i][0] = max(C[i - 1][1] + abs(B[i - 1] - 1), C[i - 1][0])
		C[i][1] = max(C[i - 1][0] + abs(B[i] - 1), C[i - 1][1] + abs(B[i] - B[i - 1]))
	return max(C[N - 1])

def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		B = [int(i) for i in input().split()]
		print(cost(N, B))
main()


import sys
T = int(sys.stdin.readline())
for case in range(T):
	N = int(sys.stdin.readline())
	BS = [int(X) for X in sys.stdin.readline().split()]
	CACHE = {(N - 1, 1): 0, (N - 1, BS[N - 1]): 0}
	for i in range(N - 2, -1, -1):
		CACHE[i, 1] = max(abs(1 - BS[i + 1]) + CACHE[i + 1, BS[i + 1]], CACHE[i + 1, 1])
		CACHE[i, BS[i]] = max(abs(1 - BS[i]) + CACHE[i + 1, 1], abs(BS[i] - BS[i + 1]) + CACHE[i + 1, BS[i + 1]])
	print(max(CACHE.values()))


from math import *
T = int(input())
for t in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	M = max(A)
	low = 0
	high = 0
	for (i, value) in enumerate(A):
		if i > 0:
			l = max(abs(1 - A[i - 1]) + high, low)
			h = max(abs(A[i] - 1) + low, abs(A[i] - A[i - 1]) + high)
			low = l
			high = h
	print(max(low, high))


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	low = 0
	high = 0
	for j in range(1, len(a)):
		l = max(abs(1 - a[j - 1]) + high, low)
		h = max(abs(a[j] - 1) + low, abs(a[j] - a[j - 1]) + high)
		low = l
		high = h
	print(max(low, high))


T = int(input())
for t in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	M = max(A)
	low = 0
	high = 0
	for (i, value) in enumerate(A):
		if i > 0:
			l = max(abs(1 - A[i - 1]) + high, low)
			h = max(abs(A[i] - 1) + low, abs(A[i] - A[i - 1]) + high)
			low = l
			high = h
	print(max(low, high))


t = int(input())
for t in range(t):
	N = int(input())
	A = [int(x) for x in input().split()]
	(ll, hh) = (0, 0)
	for (i, value) in enumerate(A):
		if i > 0:
			l = max(abs(1 - A[i - 1]) + hh, ll)
			h = max(abs(A[i] - 1) + ll, abs(A[i] - A[i - 1]) + hh)
			ll = l
			hh = h
	print(max(ll, hh))


import math
for _ in range(int(input())):
	input()
	line = list(map(int, input().split()))
	prev_low = 0
	prev_high = 0
	for i in range(1, len(line)):
		a = line[i - 1]
		b = line[i]
		x = max(abs(1 - a) + prev_high, prev_low)
		y = max(abs(b - 1) + prev_low, abs(b - a) + prev_high)
		prev_low = x
		prev_high = y
	print(max(prev_low, prev_high))


from math import ceil
T = int(input())
for cntT in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	M = max(A)
	low = 0
	high = 0
	for (i, value) in enumerate(A):
		if i > 0:
			l = max(abs(1 - A[i - 1]) + high, low)
			h = max(abs(A[i] - 1) + low, abs(A[i] - A[i - 1]) + high)
			low = l
			high = h
	print(max(low, high))


def FindASum(iArr, N):
	high = 0
	low = 0
	for i in range(1, N):
		nHigh = max(abs(1 - iArr[i]) + low, abs(iArr[i - 1] - iArr[i]) + high)
		nLow = max(abs(iArr[i - 1] - 1) + high, low)
		(high, low) = (nHigh, nLow)
	return max(high, low)
T = int(input())
for _ in range(T):
	N = int(input())
	iArr = tuple(map(int, input().split()))
	if N == 1:
		print(0)
	else:
		print(FindASum(iArr, N))


import sys
f = sys.stdin
T = int(f.readline())
for i in range(T):
	N = int(f.readline())
	tmp = f.readline().split()
	B = [int(tmp[j]) for j in range(N)]
	if N == 1:
		print('0')
		continue
	maxDiffEndWithTop = max(abs(B[1] - B[0]), abs(B[1] - 1))
	maxDiffEndWithBot = abs(1 - B[0])
	for k in range(2, N):
		newMaxDiffEndWithTop = max(maxDiffEndWithTop + abs(B[k - 1] - B[k]), maxDiffEndWithBot + abs(1 - B[k]))
		newMaxDiffEndWithBot = max(maxDiffEndWithTop + abs(B[k - 1] - 1), maxDiffEndWithBot)
		maxDiffEndWithTop = newMaxDiffEndWithTop
		maxDiffEndWithBot = newMaxDiffEndWithBot
	print(max(maxDiffEndWithTop, maxDiffEndWithBot))


t = int(input())
for i in range(t):
	n = int(input())
	b = [int(x) for x in input().split(' ')]
	sum = 0
	curr = b[0]
	dp = [[0 for x in range(2)] for y in range(n)]
	dp[0][0] = 0
	dp[0][1] = 0
	for j in range(n - 1):
		dp[j + 1][0] = max(dp[j][0] + abs(b[j + 1] - b[j]), dp[j][1] + abs(b[j + 1] - 1))
		dp[j + 1][1] = max(dp[j][0] + abs(1 - b[j]), dp[j][1] + abs(1 - 1))
	print(max(dp[n - 1][0], dp[n - 1][1]))


for _ in range(int(input())):
	N = int(input())
	B = list(map(int, input().split(' ')))
	assert len(B) == N
	if N == 1:
		print(0)
		continue
	elif N == 2:
		print(abs(max(B) - 1))
		continue
	max_cost_last_small = abs(B[0] - 1)
	max_cost_last_large = abs(1 - B[1])
	for i in range(2, N):
		max_cost_this_small = max((max_cost_last_small + abs(1 - 1), max_cost_last_large + abs(1 - B[i - 1])))
		max_cost_this_large = max((max_cost_last_small + abs(B[i] - 1), max_cost_last_large + abs(B[i] - B[i - 1])))
		(max_cost_last_small, max_cost_last_large) = (max_cost_this_small, max_cost_this_large)
	print(max((max_cost_last_small, max_cost_last_large)))


T = int(input())
for t in range(T):
	N = int(input())
	B = [int(x) for x in input().split()]
	lo = 0
	hi = 0
	for i in range(1, N):
		(lo, hi) = (max(lo, hi + abs(B[i - 1] - 1)), max(lo + abs(B[i] - 1), hi + abs(B[i] - B[i - 1])))
	print(max(lo, hi))


for game in range(int(input())):
	l = int(input())
	cap = [int(s) - 1 for s in input().split()]
	ma = [0] * l
	mi = [0] * l
	for i in range(1, l):
		ph = ma[i - 1]
		pl = mi[i - 1]
		ma[i] = max(pl + cap[i], ph + abs(cap[i] - cap[i - 1]))
		mi[i] = max(ph + cap[i - 1], pl)
	print(max(ma[-1], mi[-1]))


t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	inp = input().strip().split(' ')
	inp = [int(x) for x in inp]
	amax = [0 for i in range(n)]
	amin = [0 for i in range(n)]
	for i in range(1, n, 1):
		x = inp[i]
		amax[i] = max(amax[i - 1] + abs(inp[i] - inp[i - 1]), amin[i - 1] + inp[i] - 1)
		amin[i] = max(amax[i - 1] + inp[i - 1] - 1, amin[i - 1])
	print(max(amin[n - 1], amax[n - 1]))


t = int(input())
for _ in range(t):
	input()
	bs = iter(map(int, input().split()))
	last = next(bs)
	cost_one = 0
	cost_max = 0
	for b in bs:
		(cost_one, cost_max) = (max(cost_one, cost_max + last - 1), max(cost_max + abs(last - b), cost_one + b - 1))
		last = b
	print(max(cost_one, cost_max))


def compute_max_score(bs):
	n = len(bs)
	if 0 == n:
		return 0
	scores = dict()
	scores[0, bs[0]] = 0
	scores[0, 1] = 0
	for i in range(1, n):
		s0 = abs(bs[i] - bs[i - 1]) + scores[i - 1, bs[i - 1]]
		s1 = abs(bs[i] - 1) + scores[i - 1, 1]
		scores[i, bs[i]] = max(s0, s1)
		s0 = abs(1 - bs[i - 1]) + scores[i - 1, bs[i - 1]]
		s1 = scores[i - 1, 1]
		scores[i, 1] = max(s0, s1)
	return max(scores[n - 1, bs[n - 1]], scores[n - 1, 1])
results = list()
t = int(input())
for _ in range(t):
	n = int(input())
	bs = [int(x.strip()) for x in input().split()]
	results.append(compute_max_score(bs))
for res in results:
	print(res)


T = int(input())
for t in range(T):
	n = int(input())
	b = list(map(int, input().split()))
	dp = [[0 for c in range(2)] for r in range(n)]
	for i in range(1, n):
		dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + abs(1 - b[i - 1]))
		dp[i][1] = max(dp[i - 1][0] + abs(b[i] - 1), dp[i - 1][1] + abs(b[i] - b[i - 1]))
	print(max(dp[n - 1][0], dp[n - 1][1]))


import copy

def calculate_value(list):
	length = len(list)
	ending_in_one_values = [0 for x in range(length)]
	ending_in_max_values = [0 for x in range(length)]
	for i in range(1, length):
		ending_in_one_values[i] = max(ending_in_one_values[i - 1], ending_in_max_values[i - 1] + list[i - 1] - 1)
		ending_in_max_values[i] = max(ending_in_max_values[i - 1], ending_in_one_values[i - 1] + list[i] - 1)
	return max(ending_in_one_values[length - 1], ending_in_max_values[length - 1])

def run_test_case():
	n = int(input().strip())
	b = [int(x) for x in input().strip().split(' ')]
	print(calculate_value(b))
test_case_count = int(input().strip())
[run_test_case() for x in range(test_case_count)]


n_testcases = int(input().strip())
for _ in range(n_testcases):
	_ = input()
	B = [int(n) for n in input().strip().split()]
	best_w_1 = 0
	best_w_b = 0
	prev_b = B[0]
	for i in range(1, len(B)):
		b = B[i]
		new_best_w_1 = max(best_w_1, best_w_b + prev_b - 1)
		new_best_w_b = max(best_w_1 + b - 1, best_w_b + abs(b - prev_b))
		best_w_1 = new_best_w_1
		best_w_b = new_best_w_b
		prev_b = b
	print(max(best_w_1, best_w_b))


for _ in range(int(input())):
	n = int(input())
	B = [int(x) for x in input().split(' ')]
	low = 0
	high = 0
	for (i, value) in enumerate(B):
		if i > 0:
			l = max(abs(1 - B[i - 1]) + high, low)
			h = max(abs(B[i] - 1) + low, abs(B[i] - B[i - 1]) + high)
			low = l
			high = h
	print(max(low, high))


import sys

def sumabs(a):
	result = 0
	for i in range(1, len(a)):
		result = result + abs(a[i] - a[i - 1])
	return result

def res(A):
	low = 0
	high = 0
	for (i, value) in enumerate(A):
		if i > 0:
			l = max(abs(1 - A[i - 1]) + high, low)
			h = max(abs(A[i] - 1) + low, abs(A[i] - A[i - 1]) + high)
			low = l
			high = h
	return max(low, high)

def ans(b, n):
	if n == 1:
		return [1]
	if b[0] > b[1]:
		a = [b[0], 1]
	else:
		a = [1, b[1]]
	if n == 2:
		return a
	for i in range(2, n):
		trips = [[x, y, z] for x in [b[i - 2], 1] for y in [b[i - 1], 1] for z in [b[i], 1]]
		(s, a0) = max([(sumabs(t), t) for t in trips])
		[x0, x1, x2] = a0
		a[i - 2] = x0
		a[i - 1] = x1
		a.append(x2)
	return a
t_str = input().strip()
t = int(t_str)
for j in range(t):
	n_str = input().strip()
	n = int(n_str)
	b = [int(b_str) for b_str in input().strip().split(' ')]
	s = res(b)
	print(s)


t = int(input())

def max_val(items, n):
	total = [[0, 0] for i in range(n)]
	for i in range(0, n - 1):
		total[i + 1][0] = max(total[i][0], total[i][1] + abs(1 - items[i]))
		total[i + 1][1] = max(total[i][0] + abs(1 - items[i + 1]), total[i][1] + abs(items[i] - items[i + 1]))
	return max(total[n - 1][0], total[n - 1][1])
for i in range(t):
	items = []
	n = int(input())
	str_val = input()
	items = [int(item) for item in str_val.split()]
	print(max_val(items, n))


def shcost(B):
	low = 0
	high = 0
	for i in range(1, len(B)):
		l = max(abs(1 - B[i - 1]) + high, low)
		h = max(abs(B[i] - 1) + low, abs(B[i] - B[i - 1]) + high)
		low = l
		high = h
	return max(low, high)
T = int(input())
for tc in range(T):
	Blen = int(input())
	B = list(map(int, input().strip().split(' ')))
	print(shcost(B))


T = int(input())
for t in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	M = max(A)
	low = 0
	high = 0
	for (i, value) in enumerate(A):
		if i > 0:
			l = max(abs(1 - A[i - 1]) + high, low)
			h = max(abs(A[i] - 1) + low, abs(A[i] - A[i - 1]) + high)
			low = l
			high = h
	print(max(low, high))


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


t = int(input().strip())
for k in range(t):
	n = int(input().strip())
	limits = list(map(int, input().strip().split()))
	if n < 2:
		print(0)
		continue
	dp = [[0 for i in range(n)], [0 for i in range(n)]]
	for i in range(1, n):
		dp[0][i] = max(dp[1][i - 1] + abs(limits[i - 1] - 1), dp[0][i - 1])
		dp[1][i] = max(dp[1][i - 1] + abs(limits[i - 1] - limits[i]), dp[0][i - 1] + abs(limits[i] - 1))
	print(max(dp[0][n - 1], dp[1][n - 1]))


T = int(input())
for i in range(T):
	N = int(input())
	arr = [int(item) for item in input().split()]
	if N == 1:
		print(0)
		continue
	max_S0 = [arr[1] - 1, arr[1]]
	max_S1 = [arr[0] - 1, 1]
	for val in arr[2:]:
		if max_S0[0] + abs(val - max_S0[1]) > max_S1[0] + abs(val - max_S1[1]):
			temp_S0 = [max_S0[0] + abs(val - max_S0[1]), val]
		else:
			temp_S0 = [max_S1[0] + abs(val - max_S1[1]), val]
		if max_S0[0] + abs(max_S0[1] - 1) > max_S1[0] + abs(max_S1[1] - 1):
			temp_S1 = [max_S0[0] + abs(max_S0[1] - 1), 1]
		else:
			temp_S1 = [max_S1[0] + abs(max_S1[1] - 1), 1]
		max_S0 = temp_S0
		max_S1 = temp_S1
	print(max([max_S0[0], max_S1[0]]))


from functools import reduce
T = int(input())
for p in range(T):
	n = int(input())
	a = list(map(int, input().strip().split(' ')))
	if len(a) > 1:
		x = abs(a[0] - a[1])
		y = abs(a[0] - 1)
		z = abs(a[1] - 1)
		(sum1, sum2, sum3) = (0, 0, 0)
		for i in range(1, len(a) - 1):
			if x > z:
				xnew = x + abs(a[i] - a[i + 1])
				ynew = x + abs(a[i] - 1)
			else:
				xnew = z + abs(a[i] - a[i + 1])
				ynew = z + abs(a[i] - 1)
			z = y + abs(1 - a[i + 1])
			x = xnew
			y = ynew
		print(max(x, y, z))
	elif len(a) == 1:
		print(0)


T = int(input().strip())
for t in range(0, T):
	N = int(input().strip())
	arr = [int(item) for item in input().strip().split(' ')]
	T = [[0, 0] for item in range(0, N)]
	for i in range(1, N):
		T[i][0] = max(T[i - 1][0], T[i - 1][1] + abs(arr[i - 1] - 1))
		T[i][1] = max(T[i - 1][0] + abs(arr[i] - 1), T[i - 1][1] + abs(arr[i] - arr[i - 1]))
	print(max(T[N - 1][0], T[N - 1][1]))


for _ in range(int(input())):
	n = int(input())
	arra = list(reversed(list(map(int, input().split()))))
	low = 0
	high = 0
	for i in range(1, len(arra)):
		l = max(abs(1 - arra[i - 1]) + high, low)
		h = max(abs(1 - arra[i]) + low, abs(arra[i - 1] - arra[i]) + high)
		low = l
		high = h
	print(max(low, high))


import sys

def cost(size, B):
	dp = [[0 for _ in range(size)] for _ in range(2)]
	for i in range(1, size):
		dp[0][i] = max(abs(B[i - 1] - 1) + dp[1][i - 1], dp[0][i - 1])
		dp[1][i] = max(abs(B[i] - B[i - 1]) + dp[1][i - 1], dp[0][i - 1] + abs(B[i] - 1))
	return max(dp[0][size - 1], dp[1][size - 1])

def main():
	times = int(input(''))
	for _ in range(times):
		size = int(input(''))
		B = list(map(int, input('').split(' ')))
		print(cost(size, B))
main()


t = int(input())

def resolve(B, j, prev):
	if j == len(B):
		return 0
	if j == len(B) - 1:
		return max(abs(B[j] - prev), abs(1 - prev))
	return max(resolve(B, j + 1, 1) + abs(prev - 1), resolve(B, j + 1, B[j]) + abs(prev - B[j]))
dp = [[0, 0] for i in range(100000 + 1)]
for _ in range(t):
	n = int(input())
	B = list(map(int, input().split()))
	dp[len(B)][0] = 0
	dp[len(B)][1] = 0
	for i in range(len(B) - 1, 0, -1):
		dp[i][0] = max(dp[i + 1][1] + abs(B[i] - 1), dp[i + 1][0] + abs(1 - 1))
		dp[i][1] = max(dp[i + 1][1] + abs(B[i] - B[i - 1]), dp[i + 1][0] + abs(1 - B[i - 1]))
	print(max(dp[1][0], dp[1][1]))


def solve(n, c):
	dp1 = [0 for _ in range(101)]
	dp2 = [0 for _ in range(101)]
	for i in range(1, n):
		for j in [1, c[i]]:
			dp2[j] = abs(1 - j) + dp1[1]
			dp2[j] = max(dp2[j], abs(c[i - 1] - j) + dp1[c[i - 1]])
		for j in [1, c[i]]:
			dp1[j] = dp2[j]
	print(max(dp1))
for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	solve(n, c)


T = int(input())
for t in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	M = max(A)
	low = 0
	high = 0
	for (i, value) in enumerate(A):
		if i > 0:
			l = max(abs(1 - A[i - 1]) + high, low)
			h = max(abs(A[i] - 1) + low, abs(A[i] - A[i - 1]) + high)
			low = l
			high = h
	print(max(low, high))


t = int(input())
for _ in range(t):
	n = int(input())
	b = [int(x) for x in input().split()]
	(opt_high, opt_low) = (0, 0)
	for i in range(1, n):
		(opt_high, opt_low) = (max(opt_high + abs(b[i] - b[i - 1]), opt_low + b[i] - 1), max(opt_high + b[i - 1] - 1, opt_low))
	print(max(opt_high, opt_low))


from sys import stdin

def read_ints():
	return [int(a.strip()) for a in stdin.readline().strip().split(' ')]
(t,) = read_ints()
for t_i in range(t):
	(n,) = read_ints()
	blist = read_ints()
	prev = blist[0]
	s = [0, 0]
	for a in blist[1:]:
		s = [max(s[0], s[1] + prev - 1), max(s[0] + a - 1, s[1] + a - prev)]
		prev = a
	print(max(s))


T = int(input())
for x in range(T):
	N = int(input())
	B = [int(x) for x in input().split()]
	opt = [[0 for i in range(2)] for j in range(N)]
	for i in range(N - 1):
		opt[i + 1][0] = max(opt[i][0], opt[i][1] + abs(B[i] - 1))
		opt[i + 1][1] = max(opt[i][0] + abs(B[i + 1] - 1), opt[i][1] + abs(B[i] - B[i + 1]))
	print(max(opt[N - 1][1], opt[N - 1][0]))


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


def max_score(a):
	n = len(a)
	s = [[0] * 2 for x in range(n)]
	s[0][0] = 0
	s[0][1] = 0
	for i in range(1, n):
		s[i][0] = max(s[i - 1][0] + abs(1 - 1), s[i - 1][1] + abs(a[i - 1] - 1))
		s[i][1] = max(s[i - 1][0] + abs(1 - a[i]), s[i - 1][1] + abs(a[i - 1] - a[i]))
	return max(s[n - 1][0], s[n - 1][1])
num_probs = int(input())
for prob in range(num_probs):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(max_score(a))


import sys
T = int(input())

def solve():
	N = int(input())
	B = [int(x) for x in sys.stdin.readline().split()]
	prev_best = {1: 0}
	prev_best[B[0]] = 0
	for i in range(1, N):
		cur_best = {}
		cur_best[1] = max(prev_best[1], prev_best[B[i - 1]] + abs(B[i - 1] - 1))
		cur_best[B[i]] = max(prev_best[1] + abs(B[i] - 1), prev_best[B[i - 1]] + abs(B[i] - B[i - 1]))
		prev_best = cur_best
	print(max(prev_best.values()))
for _ in range(T):
	solve()


for _ in range(int(input())):
	n = int(input())
	B = [int(i) for i in input().strip().split()]
	(a1, s1) = (1, 0)
	(a2, s2) = (B[0], 0)
	for i in range(1, n):
		(b1, b2) = (1, B[i])
		st1 = max(abs(b1 - a1) + s1, abs(b1 - a2) + s2)
		st2 = max(abs(b2 - a1) + s1, abs(b2 - a2) + s2)
		(s1, s2) = (st1, st2)
		(a1, a2) = (b1, b2)
	print(max(s1, s2))


max1 = lambda x: x
min1 = lambda x: 1

def sub_p(l):
	mx = [0]
	mi = [0]
	for i in range(1, len(l)):
		mx.append(max(mx[i - 1] + abs(l[i - 1] - l[i]), mi[i - 1] + abs(1 - l[i])))
		mi.append(max(mx[i - 1] + abs(l[i - 1] - 1), mi[i - 1]))
	return max(mx[-1], mi[-1])
num_cases = int(input())
for i in range(num_cases):
	t = int(input())
	if t == 0:
		continue
	ab = list(map(int, input().strip().split()))
	print(sub_p(ab))


def max_s(b):
	(low, high) = (0, 0)
	for (i, _) in enumerate(b):
		if i == 0:
			continue
		l = max(abs(1 - b[i - 1]) + high, low)
		h = max(abs(b[i] - 1) + low, abs(b[i] - b[i - 1] + high))
		(low, high) = (l, h)
	return max(low, high)
t = int(input())
for _ in range(t):
	_ = int(input())
	arr = [int(token) for token in input().split()]
	print(max_s(arr))


import sys
data = sys.stdin.read()
data = data.splitlines()
data = [[int(y) for y in x.strip().split(' ')] for x in data]
T = data[0][0]
for i in range(1, T + 1, 1):
	B = data[2 * i]
	in_best_loc = [0] * len(B)
	if len(B) == 1:
		b = [0, 0]
	elif len(B) == 2:
		b = [max(B[0] - 1, B[1] - 1), 0]
	else:
		a = [B[0] - 1, 1]
		in_best_loc[0] = 1
		if B[0] - 1 > 2 * B[1] - 2:
			b = [B[0] - 1, 0]
			in_best_loc[1] = 0
		else:
			b = [2 * B[1] - 2, 1]
			in_best_loc[1] = 1
		for i in range(2, len(B) - 1, 1):
			if 2 * B[i] - 2 + a[0] > b[0]:
				c = [2 * B[i] - 2 + a[0], 1]
				in_best_loc[i] = 1
			else:
				c = [b[0], 0]
				in_best_loc[i] = 0
			a = b
			b = c
		if B[len(B) - 1] - 1 + a[0] > b[0]:
			c = [B[len(B) - 1] - 1 + a[0], 1]
			in_best_loc[len(B) - 1] = 1
			a = b
			b = c
		else:
			c = [b[0], 0]
			in_best_loc[len(B) - 1] = 0
			a = b
			b = c
	in_glob = [0] * len(B)
	next_pos = 1
	for i in range(len(B) - 1, -1, -1):
		if next_pos == 1:
			in_glob[i] = in_best_loc[i]
			if in_best_loc[i] == 1:
				next_pos = 0
			else:
				next_pos = 1
		else:
			in_glob[i] = 0
			next_pos = 1
	print(b[0])


T = int(input())
for i in range(T):
	N = int(input())
	B = list(map(int, input().split()))
	A = {'min': 0, 'max': 0}
	for i in range(1, N):
		current = {'min': 0, 'max': 0}
		current['min'] = max(A['min'], A['max'] + B[i - 1] - 1)
		current['max'] = max(A['max'] + abs(B[i - 1] - B[i]), A['min'] + B[i] - 1)
		A = current
	print(max(A['min'], A['max']))


T = int(input())
for tc in range(1, T + 1):
	N = int(input())
	v = list(map(int, input().split()))
	dph = [[v[N - 1], 0] for i in range(N)]
	dpl = [[0, 0] for i in range(N)]
	for i in range(N - 2, -1, -1):
		ndph = max(dph[i + 1][1] + abs(v[i + 1] - v[i]), dpl[i + 1][1] + v[i] - 1)
		ndpl = max(dpl[i + 1][1], dph[i + 1][1] + v[i + 1] - 1)
		dph[i][1] = ndph
		dpl[i][1] = ndpl
	ans = max(dph[0][1], dpl[0][1])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	low = 0
	high = 0
	if n > 1:
		for (i, val) in enumerate(b):
			if i > 0:
				l = abs(b[i - 1] - 1) + high
				h = max(abs(b[i] - 1) + low, abs(b[i] - b[i - 1]) + high)
				low = l
				high = h
		print(max(l, h))
	else:
		print(0)


def solve(B):
	if len(B) <= 0:
		return 0
	partials1 = [0] * 101
	partials2 = [0] * 101
	for i in range(1, len(B)):
		partials2[1] = max(partials1[1], abs(1 - B[i - 1]) + partials1[B[i - 1]])
		partials2[B[i]] = max(abs(B[i] - 1) + partials1[1], abs(B[i] - B[i - 1]) + partials1[B[i - 1]])
		temp = partials2
		partials2 = partials1
		partials1 = temp
	return max(partials1[:B[-1] + 1])
T = int(input())
while T > 0:
	N = int(input())
	B = [int(x) for x in input().split()]
	print(solve(B))
	T -= 1


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


def solve(l):
	hi_score = 0
	lo_score = 0
	for i in range(1, len(l)):
		hi1 = lo_score + abs(l[i] - 1)
		hi2 = hi_score + abs(l[i] - l[i - 1])
		lo1 = lo_score
		lo2 = hi_score + abs(l[i - 1] - 1)
		hi_score = max(hi1, hi2)
		lo_score = max(lo1, lo2)
	return max(hi_score, lo_score)
num_tests = int(input())
for t in range(num_tests):
	test_size = int(input())
	l = [int(tmp) for tmp in input().split(' ')]
	print(solve(l))


for t in range(int(input())):
	ans = 0
	n = int(input())
	b = input().split()
	b = [int(x) for x in b]
	dp = [[0, 0] for x in range(n + 1)]
	low = 0
	high = 1
	for i in range(2, n + 1):
		dp[i][low] = max(dp[i - 1][low], dp[i - 1][high] + abs(b[i - 2] - 1))
		dp[i][high] = max(dp[i - 1][high], dp[i - 1][low] + abs(b[i - 1] - 1))
	print(max(dp[n]))


from collections import deque
num_cases = int(input())
for a in range(num_cases):
	numbers_count = int(input())
	numbers = list(map(int, input().split(' ')))
	max_score_table = [[-1] * 2 for i in range(numbers_count)]
	transitions_table = [[-1] * 2 for i in range(numbers_count)]
	max_score_table[0][0] = 0
	max_score_table[0][1] = 0
	for i in range(1, len(numbers)):
		number = numbers[i]
		previous = numbers[i - 1]
		low_score_choice = max_score_table[i - 1][1] + (previous - 1)
		high_score_choice = max(max_score_table[i - 1][0] + (number - 1), max_score_table[i - 1][1] + (previous - number))
		max_score_table[i][0] = low_score_choice
		max_score_table[i][1] = high_score_choice
		transitions_table[i][0] = 1
		transitions_table[i][1] = 0
	print(max(max_score_table[-1]))


T = int(input())
for i in range(T):
	N = int(input())
	B = [int(x) for x in input().strip().split(' ')]
	DP = {(1, 0): 0, (B[0], 0): 0}
	for n in range(1, N):
		for b in [1, B[n]]:
			S = 0
			for a in [1, B[n - 1]]:
				S = max(S, DP[a, n - 1] + abs(b - a))
			DP[b, n] = S
	print(max(DP[1, N - 1], DP[B[N - 1], N - 1]))


T = int(input().strip())
for _ in range(T):
	N = int(input().strip())
	B = [1] + [int(x) for x in input().strip().split()]
	Mem = [[0 for j in range(2)] for i in range(N + 1)]
	for i in range(2, N + 1):
		Mem[i][0] = max(Mem[i - 1][0], abs(B[i - 1] - 1) + Mem[i - 1][1])
		Mem[i][1] = max(abs(B[i] - 1) + Mem[i - 1][0], abs(B[i] - B[i - 1]) + Mem[i - 1][1])
	print(max(Mem[N][0], Mem[N][1]))


t = int(input())
while t > 0:
	N = int(input())
	B = input().split()
	i = 0
	for val in B:
		B[i] = int(val)
		i += 1
	s = [0] * N
	l = [0] * N
	for i in range(1, N):
		s[i] = max(s[i - 1] + abs(B[i] - B[i - 1]), l[i - 1] + abs(B[i] - 1))
		l[i] = max(s[i - 1] + abs(B[i - 1] - 1), l[i - 1])
	t -= 1
	ans = max(s[N - 1], l[N - 1])
	print(ans)


def run():
	t = int(input().strip())
	for _ in range(t):
		n = int(input().strip())
		b = list(map(int, input().split()))
		print(max_cost(b))

def max_cost(b):
	f = [0 for i in b]
	g = [0 for i in b]
	for i in range(len(b) - 2, -1, -1):
		f[i] = max(f[i + 1], g[i + 1] + (b[i] - 1))
		g[i] = max(f[i + 1] + (b[i + 1] - 1), g[i + 1])
	return max(g[0], f[0])
run()


T = int(input())
for t in range(T):
	N = int(input())
	B = [int(num) for num in input().split()]
	used1 = not_used1 = 0
	for k in range(1, N):
		(used1, not_used1) = (max(used1, not_used1 + B[k - 1] - 1), max(used1 + B[k] - 1, not_used1 + abs(B[k] - B[k - 1])))
	print(max(used1, not_used1))


t = int(input())
for _ in range(t):
	n = int(input())
	b = [int(el) for el in input().split(' ')]
	dp = [[0, 0] for _ in range(n)]
	for i in range(1, n):
		dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + abs(b[i - 1] - 1))
		dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + abs(b[i] - 1))
	print(max(dp[-1][0], dp[-1][1]))


queries = int(input())
for i in range(queries):
	n = int(input())
	B = [int(x) for x in input().split(' ')]
	low = 0
	high = 0
	for (i, value) in enumerate(B):
		if i > 0:
			l = max(abs(1 - B[i - 1]) + high, low)
			h = max(abs(B[i] - 1) + low, abs(B[i] - B[i - 1]) + high)
			low = l
			high = h
	print(max(low, high))


import sys
test = int(input())
for nouser in range(0, test):
	n = int(input())
	vec = [int(elem) for elem in input().split(' ')]
	termino1 = 0
	terminon = 0
	for x in range(1, n):
		anterior = vec[x - 1]
		actual = vec[x]
		aux = termino1
		termino1 = terminon + anterior - 1
		terminon = max(aux + actual - 1, terminon + abs(actual - anterior))
	print(max(termino1, terminon))


T = int(input())
for T_i in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	ans = (0, 0)
	answers = [ans]
	for i in range(1, n):
		nans = (max(abs(A[i] - A[i - 1]) + ans[0], ans[1] + abs(A[i] - 1)), max(ans[1], ans[0] + abs(A[i - 1] - 1)))
		ans = nans
		answers.append(ans)
	print(max(*ans))


def calc(A, N):
	low = 0
	high = 0
	for i in range(N):
		if i > 0:
			l = max(abs(1 - A[i - 1]) + high, low)
			h = max(abs(A[i] - 1) + low, abs(A[i] - A[i - 1]) + high)
			low = l
			high = h
	return max(low, high)
T = int(input())
for i in range(T):
	res = 0
	N = int(input())
	B = list(map(int, input().split()))
	print(calc(B, N))


T = int(input())

def solve(V, N):
	mins = [0]
	maxs = [0]
	for n in range(1, N):
		mins.append(max(mins[n - 1], V[n - 1] - 1 + maxs[n - 1]))
		maxs.append(max(V[n] - 1 + mins[n - 1], V[n] - V[n - 1] + maxs[n - 1]))
	return max(mins[N - 1], maxs[N - 1])
for t in range(T):
	N = int(input())
	V = [int(v) for v in input().split()]
	print(solve(V, N))


def cost(b):
	if len(b) < 2:
		print(0)
		return
	s = [0, b[1]]
	for i in range(2, len(b)):
		s.append(max(b[i] + b[i - 2] + s[i - 2], abs(b[i] - b[i - 1]) + s[i - 1]))
	print(max(s[-1], s[-2] + b[-2]))
t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	b = [int(s) - 1 for s in input().strip().split()]
	cost(b)


T = int(input())
for _ in range(T):
	N = int(input())
	B = [int(x) for x in input().split()]
	partial_sums = [[0, 0, 0] for _ in range(N)]
	for i in range(1, N):
		picking = max(partial_sums[i - 1][1:]) + B[i] - 1
		not_picking = partial_sums[i - 1][0] + B[i - 1] - 1
		not_picking_twice = max(partial_sums[i - 1][1:])
		partial_sums[i] = [picking, not_picking, not_picking_twice]
	print(max(partial_sums[-1]))


T = int(input().strip())
for _ in range(T):
	N = int(input().strip())
	A = [int(x) for x in input().strip().split(' ')]
	(low, high) = (0, 0)
	for i in range(N):
		if i > 0:
			l = max(abs(1 - A[i - 1]) + high, low)
			h = max(abs(A[i] - 1) + low, abs(A[i] - A[i - 1]) + high)
			low = l
			high = h
	print(max(low, high))


import sys
T = int(input().strip())
for t in range(T):
	N = int(input().strip())
	B = [int(num) for num in input().strip().split(' ')]
	if N == 1:
		print(0)
		continue
	n = [0] * (N - 1)
	l = [num - 1 for num in B[:-1]]
	r = [num - 1 for num in B[1:]]
	lr = [abs(l[i] - r[i]) for i in range(N - 1)]
	for i in range(1, N - 1):
		n[N - 2 - i] += max(n[N - 1 - i], r[N - 1 - i])
		l[N - 2 - i] += max(n[N - 1 - i], r[N - 1 - i])
		lr[N - 2 - i] += max(lr[N - 1 - i], l[N - 1 - i])
		r[N - 2 - i] += max(lr[N - 1 - i], l[N - 1 - i])
	print(max(l[0], r[0]))


num_tests = int(input())
for i in range(num_tests):
	num_integers = int(input())
	integers = [int(j) for j in input().split(' ')]
	(hi, lo) = ([0], [0])
	if num_integers == 1:
		print(0)
		continue
	for j in range(1, num_integers):
		hi += [max(abs(integers[j] - integers[j - 1] + hi[j - 1]), integers[j] - 1 + lo[j - 1])]
		lo += [integers[j - 1] - 1 + hi[j - 1]]
	print(max(hi[-1], lo[-1]))


for _ in range(int(input())):
	N = int(input())
	B = list(map(int, input().split()))
	mini = [0]
	maxi = [0]
	for i in range(1, N):
		mini.append(max(mini[-1], maxi[-1] + B[i - 1] - 1))
		maxi.append(max(mini[-2] + B[i] - 1, maxi[-1] + abs(B[i] - B[i - 1])))
	print(max(mini[-1], maxi[-1]))


for _ in range(int(input())):
	(n, arr) = (int(input()), list(map(int, input().split())))
	dp = [[0, 0] for _ in range(n + 1)]
	for i in range(2, n + 1):
		dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + abs(1 - arr[i - 2]))
		dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + abs(arr[i - 1] - 1))
	print(max(dp[-1][0], dp[-1][1]))


def max_S_with_A0(b):
	b = list(b)
	possibilities = [(0, 1), (0, b.pop())]
	while b:
		b_elem = b.pop()
		low_start_possibilities = [(partial_s + abs(1 - a1), 1) for (partial_s, a1) in possibilities]
		high_start_possibilities = [(partial_s + abs(b_elem - a1), b_elem) for (partial_s, a1) in possibilities]
		possibilities = [sorted(lst)[-1] for lst in [low_start_possibilities, high_start_possibilities]]
	return sorted(possibilities)[-1]
T = int(input())
for _ in range(T):
	N = int(input())
	B = list(map(int, input().split()))
	print(max_S_with_A0(B)[0])


T = int(input().strip())

def solve(N, B):
	if N == 1:
		return 0
	S1 = 0
	S2 = 0
	for i in range(1, N):
		tmp = S1
		S1 = max(S2 + B[i - 1] - 1, tmp)
		S2 = tmp + B[i] - 1
	return max(S1, S2)
for case in range(T):
	N = int(input().strip())
	B = [int(x) for x in input().strip().split(' ')]
	print(solve(N, B))


T = int(input().strip())
for i in range(T):
	input()
	B = [int(m) for m in input().strip().split()]
	A = [1, B[0]]
	CumTally = [0, 0]
	for (I, b) in enumerate(B[1:]):
		ANew = [1, b]
		s1 = CumTally[0] + abs(ANew[0] - A[0])
		s2 = CumTally[1] + abs(ANew[0] - A[1])
		s3 = CumTally[0] + abs(ANew[1] - A[0])
		s4 = CumTally[1] + abs(ANew[1] - A[1])
		CumTally = [max([s1, s2]), max([s3, s4])]
		A = ANew
	print(max(CumTally))


def solve(B):
	N = len(B)
	assert 1 <= N <= pow(10, 5)
	assert all((1 <= b <= 100 for b in B))
	(llen, rlen) = (0, 0)
	right_pos = B[0]
	for i in range(1, N):
		new_llen = rlen + (right_pos - 1)
		new_right_pos = B[i]
		new_rlen = max(llen + (new_right_pos - 1), rlen + abs(new_right_pos - right_pos))
		(llen, rlen) = (new_llen, new_rlen)
		right_pos = new_right_pos
	return max(llen, rlen)
T = int(input())
for _ in range(T):
	N = int(input())
	B = [int(X) for X in input().split()]
	print(solve(B))


MM = 10 ** 9 + 7

def to_int_list(s):
	return list(map(int, s.split(' ')))

def compute(arr, start=0):
	previous = (0, 0)
	for i in range(1, len(arr)):
		previous = (max(previous[0], previous[1] + arr[i - 1] - 1), max(previous[0] + arr[i] - 1, previous[1] + abs(arr[i - 1]) - arr[i]))
	return max(previous[0], previous[1])
T = int(input())
for i in range(T):
	N = int(input())
	arr = to_int_list(input())
	assert N == len(arr)
	print(compute(arr))