Qpwoeirut has taken up architecture and ambitiously decided to remodel his city.

Qpwoeirut's city can be described as a row of $n$ buildings, the $i$-th ($1 \le i \le n$) of which is $h_i$ floors high. You can assume that the height of every floor in this problem is equal. Therefore, building $i$ is taller than the building $j$ if and only if the number of floors $h_i$ in building $i$ is larger than the number of floors $h_j$ in building $j$.

Building $i$ is cool if it is taller than both building $i-1$ and building $i+1$ (and both of them exist). Note that neither the $1$-st nor the $n$-th building can be cool.

To remodel the city, Qpwoeirut needs to maximize the number of cool buildings. To do this, Qpwoeirut can build additional floors on top of any of the buildings to make them taller. Note that he cannot remove already existing floors.

Since building new floors is expensive, Qpwoeirut wants to minimize the number of floors he builds. Find the minimum number of floors Qpwoeirut needs to build in order to maximize the number of cool buildings.


-----Input-----

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

The first line of each test case contains the single integer $n$ ($3 \le n \le 10^5$) — the number of buildings in Qpwoeirut's city.

The second line of each test case contains $n$ integers $h_1, h_2, \ldots, h_n$ ($1 \le h_i \le 10^9$) — the number of floors in each of the buildings of the city.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print a single integer — the minimum number of additional floors Qpwoeirut needs to build in order to maximize the number of cool buildings.


-----Examples-----

Input
6
3
2 1 2
5
1 2 1 4 3
6
3 1 4 5 5 2
8
4 2 1 3 5 3 6 1
6
1 10 1 1 10 1
8
1 10 11 1 10 11 10 1
Output
2
0
3
3
0
4


-----Note-----

In the first test case, it is optimal for Qpwoeirut to make the second building cool by building $2$ additional floors on top of it, making it taller than both of its adjacent buildings. The final heights of buildings will be $[2, \underline{3}, 2]$.

In the second test case, the number of cool buildings is already maximized, so Qpwoeirut does not need to do anything.

In the third test case, it is optimal for Qpwoeirut to make the third and fifth buildings cool by building $2$ additional floors onto the third building and $1$ additional floor onto the fifth building. The final heights of buildings will be $[3, 1, \underline{6}, 5, \underline{6}, 2]$.

It can be shown that it is impossible to make more than $2$ of the buildings cool, or to make $2$ buildings cool using fewer than $3$ additional floors.

In the fourth test case, Qpwoeirut can either make the second building cool, or he can make the third building cool. Either way, he will be building $3$ additional floors and maximizing the number of cool buildings. The final heights of buildings will be $[4, 2, \underline{4}, 3, 5, 3, 6, 1]$ or $[4, \underline{5}, 1, 3, 5, 3, 6, 1]$.

Difficulty: MEDIUM
Tags: Flows and cuts

Dynamic programming

Implementation

Greedy algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
def ss(a, n):
	count = 0
	for i in range(1, n - 1, 2):
		x = max(a[i - 1], a[i + 1])
		if a[i] <= x:
			count += x - a[i] + 1
	return count

def ff(s, n):
	lst1 = []
	lst2 = []
	for i in range(1, n - 1):
		x = max(a[i - 1], a[i + 1])
		cost = 0
		if a[i] <= x:
			cost = x - a[i] + 1
		if i % 2 == 0:
			lst1.append(cost)
		else:
			lst2.append(cost)
	x = sum(lst1)
	c = x
	for i in range(len(lst1)):
		x += lst2[i] - lst1[i]
		c = min(c, x)
	return c
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n % 2 == 1:
		print(ss(a, n))
	else:
		print(ff(a, n))


def logic(n, arr):
	if n % 2 == 0:
		a = [0] * (n - 2)
		for i in range(1, n - 1):
			a[i - 1] = max(0, 1 + max(arr[i + 1], arr[i - 1]) - arr[i])
		n = n - 2
		s = 0
		for i in range(0, n, 2):
			s += a[i]
		m = s
		for j in range(n - 2, -2, -2):
			s += a[j + 1] - a[j]
			if s < m:
				m = s
		return m
	s = 0
	for i in range(1, n, 2):
		s += max(0, 1 + max(arr[i + 1], arr[i - 1]) - arr[i])
	return s
for w in range(0, int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	print(logic(n, arr))


standard_input = '6\n3\n2 1 2\n5\n1 2 1 4 3\n6\n3 1 4 5 5 2\n8\n4 2 1 3 5 3 6 1\n6\n1 10 1 1 10 1\n8\n1 10 11 1 10 11 10 1\n'

def calcOdd(arr):
	total = 0
	for i in range(1, len(arr) - 1, 2):
		v = arr[i]
		m = max(arr[i - 1], arr[i + 1])
		if v <= m:
			total += m + 1 - v
	return total

def calcEven(arr):
	arrBackward = []
	for i in range(len(arr) - 2, 0, -2):
		v = arr[i]
		m = max(arr[i - 1], arr[i + 1])
		amount = 0
		if v <= m:
			amount = m + 1 - v
		arrBackward.append(amount)
	arrForward = []
	total = 0
	for i in range(1, len(arr) - 1, 2):
		v = arr[i]
		m = max(arr[i - 1], arr[i + 1])
		amount = 0
		if v <= m:
			amount = m + 1 - v
			total += amount
		arrForward.append(amount)
	length = len(arrForward)
	best = total
	for i in range(0, length):
		total += arrBackward[i] - arrForward[length - i - 1]
		if total < best:
			best = total
	return best
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n % 2 == 1:
		print(calcOdd(a))
	else:
		print(calcEven(a))


import itertools

def solve_odd(n, h):
	return sum((max(0, max(h[i - 1], h[i + 1]) + 1 - h[i]) for i in range(1, n, 2)))

def solve_even(n, h):
	f = [max(0, max(h[i - 1], h[i + 1]) + 1 - h[i]) for i in range(1, n - 1, 2)]
	b = [max(0, max(h[i - 1], h[i + 1]) + 1 - h[i]) for i in range(-2, -n, -2)]
	f = itertools.accumulate(f, initial=0)
	b = list(itertools.accumulate(b, initial=0))
	return min((x + y for (x, y) in zip(f, reversed(b))))
for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	print(solve_odd(n, h) if n % 2 == 1 else solve_even(n, h))


def res_odd(n, ls):
	i = 1
	h = 0
	while i < n:
		m = max(ls[i - 1], ls[i + 1])
		if m >= ls[i]:
			h += m - ls[i] + 1
		i += 2
	return h

def res_even(n, ls):
	o = []
	i = 1
	while i < n - 1:
		o.append(max(0, max(ls[i - 1], ls[i + 1]) - ls[i] + 1))
		i += 2
	e = []
	j = 2
	while j < n - 1:
		e.append(max(0, max(ls[j - 1], ls[j + 1]) - ls[j] + 1))
		j += 2
	ee = sum(e)
	mn = min(sum(o), ee)
	oo = 0
	for i in range(0, len(e)):
		ee -= e[i]
		oo += o[i]
		mn = min(mn, ee + oo)
	return mn
for _ in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	if n % 2 != 0:
		print(res_odd(n, ls))
	else:
		print(res_even(n, ls))


for i in range(int(input())):
	n = int(input())
	values = list(map(int, input().split()))
	pref = []
	suf = []
	if n % 2 != 0:
		count = 0
		for k in range(1, n - 1, 2):
			sh = values[k] - max(values[k - 1], values[k + 1]) - 1
			if sh <= 0:
				count -= values[k] - max(values[k - 1], values[k + 1]) - 1
		print(count)
	else:
		pre = 0
		su = 0
		for k in range(1, n - 1, 2):
			ch = values[k] - max(values[k - 1], values[k + 1]) - 1
			if ch <= 0:
				pre -= ch
				pref.append(pre)
			else:
				pref.append(pre)
		for k in range(n - 2, 1, -2):
			ch = values[k] - max(values[k - 1], values[k + 1]) - 1
			if ch <= 0:
				su -= ch
				suf.append(su)
			else:
				suf.append(su)
		ans = pref[n // 2 - 2]
		ch = n // 2 - 2
		for k in range(0, ch + 1):
			ans = min(ans, pref[ch - k - 1] + suf[k])
		ans = min(ans, suf[ch])
		print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = (*map(int, input().split()),)
	if n & 1:
		print(sum((max(max(arr[i - 1], arr[i + 1]) + 1 - arr[i], 0) for i in range(1, n - 1, 2))))
	else:
		presum = [0]
		for i in range(1, n - 1, 2):
			presum.append(presum[-1] + max(max(arr[i - 1], arr[i + 1]) + 1 - arr[i], 0))
		postsum = [0]
		for i in range(n - 2, 0, -2):
			postsum.append(postsum[-1] + max(max(arr[i - 1], arr[i + 1]) + 1 - arr[i], 0))
		print(min((presum[i] + postsum[-i - 1] for i in range(len(presum)))))


def resi():
	n = int(input())
	h = list(map(int, input().split()))
	if n % 2 == 1:
		fali = 0
		for i in range(1, n, 2):
			fali += max(0, max(h[i - 1], h[i + 1]) - h[i] + 1)
		print(fali)
	else:
		fali = 0
		for i in range(1, n - 1, 2):
			fali += max(0, max(h[i - 1], h[i + 1]) - h[i] + 1)
		mn = fali
		i = n - 2
		while i >= 2:
			fali += max(0, max(h[i - 1], h[i + 1]) - h[i] + 1) - max(0, max(h[i - 2], h[i]) - h[i - 1] + 1)
			if mn > fali:
				mn = fali
			i -= 2
		print(mn)
for _ in range(int(input())):
	resi()


t = int(input())
solution = []
for _ in range(t):
	n = int(input())
	h = [int(x) for x in input().split()]
	if n % 2 == 1:
		sol = 0
		for i in range(1, n - 1, 2):
			a = max(h[i - 1], h[i + 1])
			if h[i] > a:
				continue
			sol += a - h[i] + 1
		solution.append(sol)
	else:
		sol1 = 0
		sol1v = []
		sol1v.append(sol1)
		for i in range(1, n - 2, 2):
			a = max(h[i - 1], h[i + 1])
			if h[i] > a:
				sol1v.append(sol1)
				continue
			sol1 += a - h[i] + 1
			sol1v.append(sol1)
		sol2 = 0
		sol2v = []
		sol2v.append(sol2)
		for i in range(2, n - 1, 2):
			a = max(h[i - 1], h[i + 1])
			if h[i] > a:
				sol2v.append(sol2)
				continue
			sol2 += a - h[i] + 1
			sol2v.append(sol2)
		sol = min(sol2, sol1)
		for i in range(n // 2):
			sol = min(sol, sol1v[i] + sol2 - sol2v[i])
		solution.append(sol)
for sol in solution:
	print(sol)


def solve(heights):
	if len(heights) <= 2:
		return 0
	if len(heights) % 2 == 1:
		ans = 0
		for i in range(1, len(heights) - 1, 2):
			ans += max(max(heights[i - 1], heights[i + 1]) - heights[i] + 1, 0)
		return ans
	else:
		curr_floor = 0
		for i in range(len(heights) - 2, 1, -2):
			curr_floor += max(max(heights[i - 1], heights[i + 1]) - heights[i] + 1, 0)
		ans = curr_floor
		for i in range(1, len(heights) - 2, 2):
			curr_floor += max(max(heights[i - 1], heights[i + 1]) - heights[i] + 1, 0) - max(max(heights[i], heights[i + 2]) - heights[i + 1] + 1, 0)
			ans = min(ans, curr_floor)
		return ans
t = int(input())
for _ in range(t):
	n = int(input())
	heights = list(map(int, input().split()))
	print(solve(heights))


for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	c = [max(0, max(h[i - 1], h[i + 1]) + 1 - h[i]) for i in range(1, n - 1)]
	if n % 2 == 1:
		print(sum(c[::2]))
		continue
	opt = cost = sum(c[1::2])
	for i in range(0, len(c), 2):
		cost = cost + c[i] - c[i + 1]
		opt = min(opt, cost)
	print(opt)


t = int(input())
for _ in range(t):
	n = int(input())
	h = list(map(int, input().split()))
	cool_mod = [max(0, max(h[i - 1], h[i + 1]) + 1 - h[i]) for i in range(1, n - 1)]
	if n % 2 == 1:
		print(sum(cool_mod[::2]))
	else:
		left = 0
		right = sum(cool_mod[1::2])
		m = left + right
		for i in range(0, n - 2, 2):
			left += cool_mod[i]
			right -= cool_mod[i + 1]
			m = min(m, left + right)
		print(m)


import sys

def adding(th0, th1, th2):
	pivot = max(th0, th2) + 1
	return pivot - th1 if pivot > th1 else 0

def iterate(start, data):
	temp = 0
	for idx in range(start, len(data) - 1, 2):
		temp += adding(data[idx - 1], data[idx], data[idx + 1])
	return temp
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	data = list(map(int, sys.stdin.readline().split()))
	ans = iterate(1, data)
	if len(data) % 2:
		print(ans)
		continue
	temp = ans
	for i in range(n - 2, 0, -2):
		temp += adding(data[i - 1], data[i], data[i + 1])
		temp -= adding(data[i - 2], data[i - 1], data[i])
		ans = min(temp, ans)
	print(ans)


def problem(n, b):
	res = 0
	if n % 2 == 1:
		for i in range(1, n - 1, 2):
			res += needToShine(b, i)
	else:
		for i in range(1, n - 1, 2):
			res += needToShine(b, i)
		last = res
		for i in range(n - 3, 0, -2):
			last = last - needToShine(b, i) + needToShine(b, i + 1)
			res = min(res, last)
	print(res)

def needToShine(b, i):
	return max(max(b[i + 1], b[i - 1]) - b[i] + 1, 0)
cases = int(input())
for c in range(cases):
	n = int(input())
	buildings = list(map(int, input().split()))
	problem(n, buildings)


import sys
import math
input = sys.stdin.readline
from collections import defaultdict
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	k = 10 ** 9
	lst = [0] * n
	for i in range(1, n - 1):
		lst[i] = max(max(a[i - 1], a[i + 1]) - a[i] + 1, 0)
	if n % 2 == 1:
		m = 0
		for i in range(1, n, 2):
			m += lst[i]
		print(m)
	else:
		cnt = 0
		for i in range(2, n, 2):
			cnt += lst[i]
		k = cnt
		for i in range(1, n - 1, 2):
			cnt += lst[i]
			cnt -= lst[i + 1]
			k = min(cnt, k)
		print(k)


def dp(n):
	ans[0] = 0
	for i in range(1, n - 1):
		m = max(l[i - 1], l[i + 1]) - l[i] + 1
		if m < 0:
			m = 0
		if i == 1:
			ans[i] = m
			continue
		if i == 2:
			ans[i] = m
			continue
		if i % 2 == 1:
			t = ans[i - 2] + m
			ans[i] = t
		if i % 2 == 0:
			if flag[i - 3]:
				t = ans[i - 2] + m
				ans[i] = t
			else:
				if ans[i - 3] < ans[i - 2]:
					flag[i] = True
					t = ans[i - 3] + m
				else:
					t = ans[i - 2] + m
				ans[i] = t

def run():
	global l, ans, flag
	n = int(input())
	flag = [False] * n
	ans = [-1] * n
	l = list(map(int, input().split()))
	dp(n)
	if n % 2 != 0:
		print(ans[n - 2])
	else:
		print(min(ans[n - 2], ans[n - 3]))
for _ in range(int(input())):
	run()


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	low = 1
	high = n - 2
	ans = 0
	d1 = defaultdict(int)
	d2 = defaultdict(int)
	if n % 2:
		for i in range(1, n, 2):
			ans += max(0, max(l[i - 1], l[i + 1]) - l[i] + 1)
	else:
		suf = [0] * (n + 3)
		k = 0
		ans = float('inf')
		tt = 0
		for i in range(n - 2, 1, -2):
			k += max(0, max(l[i - 1], l[i + 1]) - l[i] + 1)
			suf[i] = k
			tt = k
		k = 0
		for i in range(1, n - 1, 2):
			k += max(0, max(l[i - 1], l[i + 1]) - l[i] + 1)
			ans = min(ans, k + suf[i + 3])
		k = 0
		ans = min(ans, tt)
	print(ans)


import sys
maxSize = sys.maxsize
t = int(input())
while t:
	p = int(input())
	h = list(map(int, input().split()))
	cool_mod = [max(0, max(h[i - 1], h[i + 1]) + 1 - h[i]) for i in range(1, p - 1)]
	if p % 2 == 1:
		print(sum(cool_mod[::2]))
	else:
		left = 0
		right = sum(cool_mod[1::2])
		m = left + right
		for i in range(0, p - 2, 2):
			left += cool_mod[i]
			right -= cool_mod[i + 1]
			m = min(m, left + right)
		print(m)
	t -= 1


t = int(input())

def solve():
	n = int(input())
	lst = list(map(int, input().split()))
	ans = 0
	if n & 1:
		for i in range(1, n, 2):
			ans += max(0, max(lst[i + 1] - lst[i] + 1, lst[i - 1] - lst[i] + 1))
	else:
		prefix = [0] * n
		suffix = [0] * n
		for i in range(1, n - 1, 2):
			prefix[i] = max(0, max(lst[i + 1] - lst[i] + 1, lst[i - 1] - lst[i] + 1))
		for i in range(n - 2, 0, -2):
			suffix[i] = max(0, max(lst[i + 1] - lst[i] + 1, lst[i - 1] - lst[i] + 1))
		for i in range(3, n - 1, 2):
			prefix[i] += prefix[i - 2]
		for i in range(n - 4, 0, -2):
			suffix[i] += suffix[i + 2]
		ans = -1
		for i in range(0, n, 2):
			if i == 0:
				sum = suffix[2]
			elif i == n - 2:
				sum = prefix[n - 3]
			else:
				sum = suffix[i + 2] + prefix[i - 1]
			if ans == -1:
				ans = sum
			else:
				ans = min(ans, sum)
	print(ans)
while t:
	solve()
	t -= 1


t = int(input())
for T in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if n % 2 != 0:
		ans = 0
		for i in range(1, n, 2):
			q = max(arr[i - 1], arr[i + 1])
			ans += max(0, q - arr[i] + 1)
		print(ans)
	else:
		dp = [0] * n
		dp[1] = max(0, max(arr[0], arr[2]) - arr[1] + 1)
		if n > 3:
			dp[2] = max(0, max(arr[1], arr[3]) - arr[2] + 1)
		for i in range(3, n - 1, 2):
			q = max(arr[i - 1], arr[i + 1])
			dp[i] = dp[i - 2] + max(0, q - arr[i] + 1)
		for i in range(4, n - 1, 2):
			q = max(arr[i - 1], arr[i + 1])
			v = min(dp[i - 2], dp[i - 3])
			dp[i] = v + max(0, q - arr[i] + 1)
		print(min(dp[n - 2], dp[n - 3]))


def helper(i):
	return max(1 + max(l[i - 1], l[i + 1]) - l[i], 0)
for caseno in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n % 2:
		answer = 0
		for i in range(1, n - 1, 2):
			answer += helper(i)
	else:
		(a, b) = (0, 0)
		for i in range(1, n - 1, 2):
			(c, d) = (helper(i), helper(i + 1))
			(a, b) = (c + a, min(a, b) + d)
		answer = min(a, b)
	print(answer)


def p(s):
	pass

def f(h):
	l = len(h)
	c = [0 for _ in h]
	i = 1
	best = 0
	while i < l - 1:
		x = max(h[i - 1], h[i + 1])
		if h[i] <= x:
			c[i] = x - h[i] + 1
		if i % 2:
			best += c[i]
		i += 1
	p(best)
	p(c)
	if l % 2:
		p(f'--best:{best}')
		print(best)
		return
	cur = best
	while i > 0:
		cur = cur - c[i - 2] + c[i - 1]
		if cur < best:
			best = cur
		i -= 2
	p(f'best:{best}')
	print(best)
for _ in range(int(input())):
	n = int(input())
	h = [int(_) for _ in input().split()]
	f(h)


out = []
for _ in range(int(input())):
	n = int(input())
	h = [int(i) for i in input().split()]
	ans = 0
	if n % 2 == 1:
		for i in range(1, n - 1, 2):
			ans += max(0, max(h[i - 1], h[i + 1]) + 1 - h[i])
	else:
		ev = [0]
		od = [0]
		for i in range(1, n - 1, 2):
			ev.append(ev[-1] + max(0, max(h[i - 1], h[i + 1]) + 1 - h[i]))
		for i in range(2, n, 2):
			od.append(od[-1] + max(0, max(h[i - 1], h[i + 1]) + 1 - h[i]))
		ans = ev[-1]
		for i in range(len(ev)):
			ans = min(ans, ev[i] + od[-1] - od[i])
	out.append(ans)
for i in out:
	print(i)


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	ans = 0
	for i in range(1, n - 1, 2):
		ma = max(nums[i - 1], nums[i + 1])
		if nums[i] <= ma:
			ans += ma - nums[i] + 1
	if not n % 2:
		su = ans
		for i in range(n - 2, 0, -2):
			ma = max(nums[i], nums[i - 2])
			if nums[i - 1] <= ma:
				su -= ma - nums[i - 1] + 1
			ma1 = max(nums[i - 1], nums[i + 1])
			if nums[i] <= ma1:
				su += ma1 - nums[i] + 1
			ans = min(ans, su)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	if n % 2 == 1:
		temp = 0
		for i in range(1, n, 2):
			temp += max(max(h[i - 1], h[i + 1]) + 1 - h[i], 0)
		print(temp)
	else:
		lgap = [max(max(h[i - 1], h[i + 1]) + 1 - h[i], 0) for i in range(1, n - 1, 2)]
		rgap = [max(max(h[i - 1], h[i + 1]) + 1 - h[i], 0) for i in range(2, n, 2)]
		k = len(rgap)
		for i in range(1, k):
			lgap[i] += lgap[i - 1]
			rgap[k - 1 - i] += rgap[k - i]
		temp = min(lgap[-1], rgap[0])
		for i in range(0, k - 1):
			temp = min(temp, lgap[i] + rgap[i + 1])
		print(temp)


t = int(input())
for vvod in range(t):
	n = int(input())
	v = list(map(int, input().split()))
	ans = 0
	ans1 = 0
	ans2 = 0
	m = [0 for i in range(n)]
	if n % 2 == 1:
		for i in range(1, n - 1, 2):
			maxim = max(v[i - 1], v[i + 1])
			if v[i] <= maxim:
				ans += maxim - v[i] + 1
		print(ans)
	else:
		ansl = list()
		for i in range(2, n - 1, 2):
			maxim = max(v[i - 1], v[i + 1])
			if v[i] <= maxim:
				m[i] = maxim - v[i] + 1
				ans += m[i]
		ans1 = ans
		ans2 = ans
		for i in range(1, n - 1, 2):
			maxim = max(v[i - 1], v[i + 1])
			if v[i] <= maxim:
				ans1 += maxim - v[i] + 1 - m[i + 1]
				ans2 = min(ans2, ans1)
			else:
				ans1 -= m[i + 1]
				ans2 = min(ans2, ans1)
		print(ans2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n % 2:
		ans = 0
		for i in range(1, n - 1, 2):
			m = max(a[i - 1], a[i + 1])
			if m >= a[i]:
				ans += m - a[i] + 1
		print(ans)
	else:
		temp = [i for i in a]
		start = [0]
		end = [0]
		for i in range(1, n - 1, 2):
			x = 0
			m = max(a[i - 1], a[i + 1])
			if m >= a[i]:
				x = m - a[i] + 1
			start.append(start[-1] + x)
		a = [i for i in temp]
		for i in range(n - 2, 1, -2):
			x = 0
			m = max(a[i - 1], a[i + 1])
			if m >= a[i]:
				x = m - a[i] + 1
			end.append(end[-1] + x)
		end = end[::-1]
		ans = float('inf')
		for i in range(len(start)):
			ans = min(ans, start[i] + end[i])
		print(ans)


for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	ans = 0
	if n % 2 == 1:
		for i in range(1, n - 1, 2):
			ans += max(h[i - 1] - h[i] + 1, h[i + 1] - h[i] + 1, 0)
	else:
		prefix_odd = [0] * (n // 2)
		prefix_even = [0] * (n // 2)
		for i in range(1, n - 1, 2):
			prefix_odd[(i + 1) // 2] = prefix_odd[i // 2] + max(h[i - 1] - h[i] + 1, h[i + 1] - h[i] + 1, 0)
		for i in range(n - 2, 0, -2):
			prefix_even[i // 2 - 1] = prefix_even[i // 2] + max(h[i - 1] - h[i] + 1, h[i + 1] - h[i] + 1, 0)
		ans = float('inf')
		for i in range(n // 2):
			ans = min(ans, prefix_even[i] + prefix_odd[i])
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	h = list(map(int, input().split()))
	if n % 2 == 0:
		x = int(n / 2) - 1
		temp = list(map(int, [0] * n))
		for i in range(1, n - 1):
			temp[i] = max(0, max(h[i - 1], h[i + 1]) - h[i] + 1)
		cnt = 0
		for i in range(1, x * 2, 2):
			cnt += temp[i]
		tt = cnt
		for k in range(n - 3, -1, -2):
			tt += temp[k + 1] - temp[k]
			cnt = min(tt, cnt)
		print(cnt)
	else:
		x = n // 2
		cnt = 0
		for i in range(1, 2 * x, 2):
			cnt += max(max(h[i - 1], h[i + 1]) - h[i] + 1, 0)
		print(cnt)


t = int(input())
for jj in range(t):
	n = int(input())
	p = [int(i) for i in input().split(' ')]
	if n % 2 == 1:
		ans = 0
		for i in range(1, n, 2):
			ans += max(max(p[i - 1], p[i + 1]) + 1 - p[i], 0)
	else:
		pre = [0] * n
		for i in range(1, n - 1, 2):
			if i == 1:
				pre[i] = max(max(p[i - 1], p[i + 1]) + 1 - p[i], 0)
			else:
				pre[i] = pre[i - 2] + max(max(p[i - 1], p[i + 1]) + 1 - p[i], 0)
		ans = pre[n - 3]
		t = 0
		for i in range(n - 2, 0, -2):
			t += max(max(p[i - 1], p[i + 1]) + 1 - p[i], 0)
			if i > 2:
				ans = min(ans, t + pre[i - 3])
			else:
				ans = min(ans, t)
	print(ans)


def get(arr, i):
	return max(0, max(arr[i + 1], arr[i - 1]) - arr[i] + 1)

def main():
	T = int(input())
	for _ in range(T):
		n = int(input())
		a = [int(i) for i in input().split()]
		a.append(0)
		count = 0
		if n % 2 != 0:
			for i in range(1, n - 1, 2):
				count += get(a, i)
		else:
			total = 0
			for i in range(1, n - 1, 2):
				total += get(a, i)
			count = total
			for i in range(n - 2, 0, -2):
				total -= get(a, i - 1)
				total += get(a, i)
				count = min(count, total)
		print(count)
main()


def solve(n, heights):
	if n % 2 == 1:
		cnt = 0
		for i in range(1, n - 1, 2):
			cnt += max(max(heights[i - 1], heights[i + 1]) - heights[i] + 1, 0)
		return cnt
	else:
		m = n // 2 - 1
		blocks = [0] * m
		shifted_blocks = [0] * m
		for i in range(m):
			j = 1 + 2 * i
			k = 2 + 2 * i
			if heights[j] > heights[j - 1] and heights[j] > heights[j + 1]:
				pass
			else:
				blocks[i] = max(heights[j - 1], heights[j + 1]) - heights[j] + 1
			if heights[k] > heights[k - 1] and heights[k] > heights[k + 1]:
				pass
			else:
				shifted_blocks[i] = max(heights[k - 1], heights[k + 1]) - heights[k] + 1
		current = solve(n - 1, heights[:-1])
		min_cost = current
		for i in reversed(range(m)):
			delta = -blocks[i] + shifted_blocks[i]
			current += delta
			if current < min_cost:
				min_cost = current
		return min_cost
tests = int(input())
for _ in range(tests):
	n = int(input())
	array = list(map(int, input().split()))
	a = solve(n, array)
	print(a)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	for i in range(1, n - 1):
		l1.append(max(0, max(l[i - 1], l[i + 1]) + 1 - l[i]))
	if n % 2 == 1:
		print(sum(l1[::2]))
		continue
	a = sum(l1[1::2])
	b = a
	for i in range(0, len(l1), 2):
		b += l1[i] - l1[i + 1]
		a = min(a, b)
	print(a)


for t in range(int(input())):
	n = int(input())
	s = [*map(int, input().split())]
	l = []
	for i in range(1, n - 1):
		l.append(max(0, max(s[i - 1], s[i + 1]) + 1 - s[i]))
	if n % 2 == 1:
		print(sum(l[::2]))
		continue
	a = sum(l[1::2])
	b = a
	for i in range(0, len(l), 2):
		b += l[i] - l[i + 1]
		a = min(a, b)
	print(a)


for _ in range(int(input())):
	n = int(input())
	arr = input().split(' ')
	arr = [int(i) for i in arr]
	if n % 2:
		ind = 1
		ans = 0
		while ind <= n - 2:
			ans += max(0, 1 + max(arr[ind - 1], arr[ind + 1]) - arr[ind])
			ind += 2
		print(ans)
		continue
	else:
		(b, c) = ([], [])
		for i in range(1, n - 1):
			if i % 2:
				b.append(max(0, 1 + max(arr[i - 1], arr[i + 1]) - arr[i]))
			else:
				c.append(max(0, 1 + max(arr[i - 1], arr[i + 1]) - arr[i]))
		ans = sum(c)
		ansmax = ans
		for i in range(len(b)):
			ans = ans + b[i] - c[i]
			ansmax = min(ans, ansmax)
		print(ansmax)


from math import inf
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n % 2 == 1:
		ans = 0
		for i in range(1, len(a) - 1, 2):
			ans += max(0, 1 + max(a[i - 1], a[i + 1]) - a[i])
		print(ans)
	else:
		ans = inf
		b = [0]
		for i in range(1, n - 1):
			b.append(max(0, 1 + max(a[i - 1], a[i + 1]) - a[i]))
		b.append(0)
		pre = [0]
		for i in range(1, n - 1, 2):
			pre.append(pre[-1] + b[i])
		suf = [0]
		for i in range(n - 2, 0, -2):
			suf.append(suf[-1] + b[i])
		suf.reverse()
		total = n // 2
		total -= 1
		for i in range(0, len(pre)):
			ans = min(ans, pre[i] + suf[i])
		print(ans)


def add(i):
	mark1 = 0
	mark2 = 0
	if h[i - 1] >= h[i]:
		mark1 = h[i - 1] - h[i] + 1
	if h[i + 1] >= h[i]:
		mark2 = h[i + 1] - h[i] + 1
	return max(mark1, mark2)
T = int(input())
for _ in range(T):
	n = int(input())
	h = list(map(int, input().split()))
	if n % 2 == 1:
		ans = 0
		for i in range(1, n - 1, 2):
			ans += add(i)
		print(ans)
	else:
		left = [0]
		right = [0]
		start_left = 0
		start_right = 0
		for i in range(1, n - 1, 2):
			start_left += add(i)
			left.append(start_left)
		for i in range(2, n - 1, 2):
			start_right += add(i)
			right.append(start_right)
		total_left = left[-1]
		total_right = right[-1]
		ans = left[0] + total_right - right[0]
		for i in range(len(left)):
			ans = min(ans, left[i] + total_right - right[i])
		print(ans)


def rebuild(x, l):

	def floor(v):
		s = max(l[v - 1] - l[v], l[v + 1] - l[v])
		if s >= 0:
			return s + 1
		else:
			return 0
	if x % 2 == 1:
		ans = 0
		for i in range(x // 2):
			ans += floor(2 * i + 1)
		return ans
	else:
		N = x // 2 - 1
		dp = 0
		for j in range(N):
			dp += floor(2 * (j + 1))
		ans = dp
		for k in range(N):
			dp += floor(2 * k + 1) - floor(2 * k + 2)
			ans = min(ans, dp)
		return ans
nCases = int(input())
for _ in range(nCases):
	n = int(input())
	h = list(map(int, input().split()))
	print(rebuild(n, h))


t = int(input())

def addFloor(i: int) -> int:
	return max(h[i - 1] + 1 - h[i], h[i + 1] + 1 - h[i], 0)
for _ in range(t):
	n = int(input())
	h = list(map(int, input().split()))
	ans = 10 ** 9 * 10 ** 5
	dp = [0] * n
	for i in range(2, n):
		dp[i] = dp[i - 2] + addFloor(i - 1)
	if n & 1:
		ans = dp[n - 1]
	else:
		for i in range(0, n, 2):
			ans = min(ans, dp[n - 1] + dp[i] - dp[i + 1])
	print(ans)


def miis():
	return map(int, input().split())
for _ in range(int(input())):
	n = int(input())
	a = list(miis())
	if n % 2:
		ans = 0
		for i in range(1, n, 2):
			ans += max(0, max(a[i + 1], a[i - 1]) + 1 - a[i])
		print(ans)
	else:
		dp = [0 for i in range(n)]
		for i in range(1, n - 1):
			dp[i] = dp[i - 2] + max(0, max(a[i + 1], a[i - 1]) + 1 - a[i])
		ans = min(dp[-2], dp[-3])
		for i in range(1, n - 3, 2):
			ans = min(ans, dp[i] + dp[-2] - dp[i + 1])
		print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	height = [int(i) for i in input().split()]
	if n % 2 == 1:
		ans = 0
		for j in range(1, n, 2):
			ans += max(height[j - 1] - height[j] + 1, height[j + 1] - height[j] + 1, 0)
		print(ans)
	else:
		ans = 0
		for j in range(1, n - 1, 2):
			ans += max(height[j - 1] - height[j] + 1, height[j + 1] - height[j] + 1, 0)
		arr = [ans]
		k = 0
		for j in range(n - 3, 0, -2):
			temp = arr[k] - max(height[j - 1] - height[j] + 1, height[j + 1] - height[j] + 1, 0) + max(height[j] - height[j + 1] + 1, height[j + 2] - height[j + 1] + 1, 0)
			arr.append(temp)
			k += 1
		print(min(arr))


import math
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	odd = [float('inf')] * math.ceil((n - 1) // 2)
	even = [float('inf')] * math.ceil((n - 1) // 2)
	j = 0
	for i in range(1, n - 1, 2):
		odd[j] = max(0, 1 + max(arr[i - 1], arr[i + 1]) - arr[i])
		j += 1
	if n % 2 == 0:
		j = 0
		for i in range(2, n - 1, 2):
			even[j] = max(0, 1 + max(arr[i - 1], arr[i + 1]) - arr[i])
			j += 1
	for i in range(len(odd) - 2, -1, -1):
		odd[i] += min(odd[i + 1], even[i + 1])
		even[i] += even[i + 1]
	print(min(odd[0], even[0]))


def increase_tower_height(num):
	new_floors = max(towers_heights[num - 1], towers_heights[num + 1]) - towers_heights[num] + 1
	if new_floors > 0:
		return new_floors
	else:
		return 0
for _ in range(int(input())):
	n = int(input())
	towers_heights = [int(i) for i in input().split()]
	if n % 2 == 0:
		dict = {}
		min_sum_even = 0
		for i in range(1, n - 1, 2):
			min_sum_even += increase_tower_height(i)
		i = n - 2
		sum_even = min_sum_even
		while i > 0:
			sum_even += increase_tower_height(i)
			sum_even -= increase_tower_height(i - 1)
			i -= 2
			min_sum_even = min(sum_even, min_sum_even)
		print(min_sum_even)
	else:
		sum = 0
		i = 1
		while i < n - 1:
			sum += increase_tower_height(i)
			i += 2
		print(sum)


t = int(input())
for tt in range(t):
	n = int(input())
	h = [int(x) for x in input().split()]
	arr = [0] * n
	flag0 = 0
	flag1 = 0
	for i in range(n - 2, 0, -1):
		if i % 2 == 0:
			if flag0 == 0:
				arr[i] = max(h[i - 1] - h[i] + 1, h[i + 1] - h[i] + 1, 0)
				flag0 = 1
			else:
				arr[i] = arr[i + 2] + max(h[i - 1] - h[i] + 1, h[i + 1] - h[i] + 1, 0)
		elif flag1 == 0:
			arr[i] = max(h[i - 1] - h[i] + 1, h[i + 1] - h[i] + 1, 0)
			flag1 = 1
		else:
			arr[i] = arr[i + 2] + max(h[i - 1] - h[i] + 1, h[i + 1] - h[i] + 1, 0)
	if len(h) % 2 == 0:
		ans = arr[1]
		for i in range(1, n - 1, 2):
			ans = min(ans, arr[1] - arr[i] + arr[i + 1])
	else:
		ans = arr[1]
	print(ans)


in_il = lambda : list(map(lambda x: int(x), input().split(' ')))
in_sl = lambda : input().split(' ')
in_i = lambda : int(input())

def cost(buildings, i):
	if buildings[i - 1] < buildings[i] and buildings[i + 1] < buildings[i]:
		return 0
	return max(buildings[i - 1], buildings[i + 1]) - buildings[i] + 1
for _ in range(in_i()):
	n = in_i()
	buildings = in_il()
	if n % 2 != 0:
		ops = 0
		for i in range(1, n - 1)[::2]:
			if buildings[i - 1] >= buildings[i] or buildings[i + 1] >= buildings[i]:
				ops += max(buildings[i - 1], buildings[i + 1]) - buildings[i] + 1
		print(ops)
	else:
		prefix = [0] * n
		sufix = [0] * n
		i = 2
		while i + 1 < n:
			prefix[i] = prefix[i - 2] + cost(buildings, i - 1)
			i += 2
		i = n - 3
		while i - 1 >= 0:
			sufix[i] = sufix[i + 2] + cost(buildings, i + 1)
			i -= 2
		ops = float('inf')
		for i in range(0, n, 2):
			ops = min(ops, prefix[i] + sufix[i + 1])
		print(ops)


from sys import prefix
t = int(input())
for _ in range(t):
	n = int(input())
	h = [int(x) for x in input().split()]
	if n % 2:
		sol = 0
		for i in range(1, n, 2):
			(a, b, c) = (h[i - 1], h[i], h[i + 1])
			if b <= a or b <= c:
				sol += max(a, c) - b + 1
	else:
		sol = -1
		count = int((n - 1) / 2)
		costs = {0: 0, n - 1: 0}
		for i in range(1, n - 1):
			(a, b, c) = (h[i - 1], h[i], h[i + 1])
			if b <= a or b <= c:
				costs[i] = max(a, c) - b + 1
			else:
				costs[i] = 0
		prefix_sums = [0]
		for i in range(count):
			prefix_sums.append(prefix_sums[-1] + costs[2 * i + 1])
		suffix_sums = [sum((costs[n - 2 * i] for i in range(1, count + 1)))]
		for i in range(count, 0, -1):
			suffix_sums.append(suffix_sums[-1] - costs[n - 2 * i])
		for i in range(0, int(n / 2)):
			curr = prefix_sums[i] + suffix_sums[i]
			if sol == -1 or sol > curr:
				sol = curr
	print(sol)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n % 2 != 0:
		sol = 0
		for i in range(1, n - 1):
			if i % 2 == 0:
				continue
			sol += max(0, max(a[i - 1], a[i + 1]) + 1 - a[i])
		print(sol)
	else:
		sol = 0
		for i in range(1, n - 2):
			if i % 2 == 0:
				continue
			sol += max(0, max(a[i - 1], a[i + 1]) + 1 - a[i])
		ans = sol
		for i in range(n - 3, -1, -2):
			sol += a[i] - max(a[i - 1] + 1, a[i + 1] + 1, a[i]) + (max(a[i + 2] + 1, a[i] + 1, a[i + 1]) - a[i + 1])
			ans = min(ans, sol)
		print(ans)


N = int(input())
for _ in range(N):
	n = int(input())
	a = list(map(int, input().split()))
	if n % 2:
		ans = 0
		for i in range(1, n - 1, 2):
			ans += max(max(a[i - 1], a[i + 1]) + 1 - a[i], 0)
		print(ans)
	else:
		ans = float('inf')
		j = 1
		pr1 = [0] * n
		pr2 = [0] * n
		for i in range(1, n - 1, 2):
			r = max(max(a[i - 1], a[i + 1]) + 1 - a[i], 0)
			pr1[j] = pr1[j - 1] + r
			j += 1
		j = 1
		for i in range(2, n - 1, 2):
			r = max(max(a[i - 1], a[i + 1]) + 1 - a[i], 0)
			pr2[j] = pr2[j - 1] + r
			j += 1
		for i in range(n // 2):
			ans = min(ans, pr1[i] + pr2[n // 2 - 1] - pr2[i])
		print(ans)


for i in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	diff_arr = []
	for i in range(1, n - 1):
		diff_arr.append(max(0, max(arr[i - 1] - arr[i] + 1, arr[i + 1] - arr[i] + 1)))
	if n % 2 == 1:
		res = 0
		for i in range(0, len(diff_arr), 2):
			res += diff_arr[i]
		print(res)
	else:
		pos_res = []
		half = len(diff_arr) // 2
		green = [diff_arr[i] for i in range(len(diff_arr)) if i % 2 == 0]
		red = [diff_arr[i] for i in range(len(diff_arr)) if i % 2 == 1]
		green_sum = 0
		red_sum = sum(red)
		for i in range(half + 1):
			pos_res.append(green_sum + red_sum)
			if i < half:
				red_sum -= red[i]
				green_sum += green[i]
		print(min(pos_res))


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if n % 2:
		ans = 0
		for j in range(1, n, 2):
			ans += 0 if arr[j] > arr[j - 1] and arr[j] > arr[j + 1] else 1 + max(arr[j - 1], arr[j + 1]) - arr[j]
		print(ans)
	else:
		pref = [0] * (n // 2)
		suf = [0] * (n // 2)
		for j in range(n // 2 - 1):
			ind = j * 2 + 1
			pref[j + 1] = pref[j] + (0 if arr[ind] > arr[ind - 1] and arr[ind] > arr[ind + 1] else 1 + max(arr[ind - 1], arr[ind + 1]) - arr[ind])
		for j in range(n // 2 - 1):
			ind = n - (j * 2 + 2)
			suf[j + 1] = suf[j] + (0 if arr[ind] > arr[ind - 1] and arr[ind] > arr[ind + 1] else 1 + max(arr[ind - 1], arr[ind + 1]) - arr[ind])
		ans = 10 ** 20
		for j in range(n // 2):
			ans = min(ans, pref[j] + suf[n // 2 - j - 1])
		print(ans)


import sys
from heapq import heappop, heappush
input = sys.stdin.readline
for t in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	if n & 1:
		ans = 0
		for i in range(1, n - 1, 2):
			m = max(0, a[i - 1] + 1 - a[i], a[i + 1] + 1 - a[i])
			ans += m
		print(ans)
	else:
		ans = 10 ** 9
		pops = []
		(odd, even) = ([], [])
		for i in range(1, n - 1):
			m = max(0, a[i - 1] + 1 - a[i], a[i + 1] + 1 - a[i])
			if i & 1:
				odd.append(m)
			else:
				even.append(m)
		for i in range(1, len(odd)):
			odd[i] += odd[i - 1]
			even[len(odd) - i - 1] += even[len(odd) - i]
		ans = min(odd[-1], even[0])
		for i in range(len(odd) - 1):
			ans = min(ans, odd[i] + even[i + 1])
		print(ans)


t = int(input())
for asd in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if n % 2 == 1:
		i = 1
		cost = 0
		while i < n - 1:
			if max(arr[i - 1], arr[i + 1]) >= arr[i]:
				cost += max(arr[i - 1], arr[i + 1]) - arr[i] + 1
			i += 2
		print(cost)
	else:
		i = 1
		cost1 = {}
		cost = 0
		while i < n - 1:
			if max(arr[i - 1], arr[i + 1]) >= arr[i]:
				cost += max(arr[i - 1], arr[i + 1]) - arr[i] + 1
			cost1[i] = cost
			i += 2
		i = n - 2
		cost2 = {}
		cost = 0
		while i > 0:
			if max(arr[i - 1], arr[i + 1]) >= arr[i]:
				cost += max(arr[i - 1], arr[i + 1]) - arr[i] + 1
			cost2[i] = cost
			i -= 2
		final = max(cost2.values())
		for i in cost1:
			if i + 3 in cost2:
				final = min(final, cost1[i] + cost2[i + 3])
			else:
				final = min(final, cost1[i])
		print(final)


import sys
t = int(sys.stdin.readline())
for i in range(t):
	n = int(sys.stdin.readline())
	lst = list(map(int, sys.stdin.readline().split()))
	lst1 = []
	for j in range(1, n - 1):
		ele = max(lst[j - 1], lst[j + 1]) + 1
		if lst[j] >= ele:
			lst1.append(0)
		else:
			lst1.append(ele - lst[j])
	lst1.append(0)
	lst1 = [0] + lst1
	pre = [lst1[0], lst1[1], lst1[2]]
	for j in range(3, n):
		pre.append(pre[-2] + lst1[j])
	dp = [1e+18] * n
	for i in range(1, n - 1):
		if i % 2 != 0:
			dp[i] = pre[i]
		elif i - 2 == 0:
			dp[i] = min(lst1[i], pre[i - 1])
		else:
			dp[i] = min(lst1[i] + dp[i - 2], pre[i - 1])
	print(dp[n - 2])


test = int(input())
while test:
	n = int(input())
	a = [int(x) for x in input().split()]
	ans = 0
	if n % 2:
		ans = 0
		for i in range(1, n, 2):
			ans += max(0, max(a[i - 1] - a[i] + 1, a[i + 1] - a[i] + 1))
	else:
		ans = float('inf')
		prefix_odd = [0] * n
		suffix_even = [0] * n
		prefix_odd[1] = max(0, max(a[0] - a[1] + 1, a[2] - a[1] + 1))
		suffix_even[n - 2] = max(0, max(a[n - 3] - a[n - 2] + 1, a[n - 1] - a[n - 2] + 1))
		for i in range(3, n - 1, 2):
			prefix_odd[i] = prefix_odd[i - 2] + max(0, max(a[i - 1] - a[i] + 1, a[i + 1] - a[i] + 1))
			suffix_even[n - i - 1] = suffix_even[n - i + 1] + max(0, max(a[n - i - 2] - a[n - i - 1] + 1, a[n - i] - a[n - i - 1] + 1))
		for i in range(0, n, 2):
			if i == 0:
				ans = min(ans, suffix_even[i + 2])
			elif i == n - 2:
				ans = min(ans, prefix_odd[i - 1])
			else:
				ans = min(ans, suffix_even[i + 2] + prefix_odd[i - 1])
	print(ans)
	test -= 1


t = int(input())
while t >= 1:
	n = int(input())
	a = list(map(int, input().split()))
	left = []
	right = []
	if n % 2 == 0:
		for i in range(1, len(a) - 1, 2):
			if a[i] > a[i - 1] and a[i] > a[i + 1]:
				left.append(0)
			else:
				floors = max(a[i - 1], a[i + 1]) - a[i] + 1
				left.append(floors)
		for i in range(2, len(a) - 1, 2):
			if a[i] > a[i - 1] and a[i] > a[i + 1]:
				right.append(0)
			else:
				floors = max(a[i - 1], a[i + 1]) - a[i] + 1
				right.append(floors)
		for i in range(1, len(left)):
			left[i] += left[i - 1]
			right[i] += right[i - 1]
		ans = min(left[-1], right[-1])
		for i in range(len(left) - 1):
			ans = min(ans, left[i] + (right[-1] - right[i]))
		print(ans)
	else:
		ans = 0
		for i in range(1, len(a) - 1, 2):
			if a[i] > a[i - 1] and a[i] > a[i + 1]:
				ans += 0
			else:
				floors = max(a[i - 1], a[i + 1]) - a[i] + 1
				ans += floors
		print(ans)
	t -= 1


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c1 = 0
	c2 = 0
	c = [[0] * n for i in range(2)]
	for i in range(n):
		if i % 2 == 1 and i != n - 1 and (i != 0):
			c1 += max(0, max(a[i - 1] - a[i], a[i + 1] - a[i]) + 1)
		c[0][i] = c1
	if n % 2:
		print(c1)
		continue
	for i in range(n - 1, -1, -1):
		if i % 2 == 0 and i != 0 and (i != n - 1):
			c2 += max(0, max(a[i - 1] - a[i], a[i + 1] - a[i]) + 1)
		c[1][i] = c2
	ans = min(c1, c2)
	for i in range(2, n - 3, 2):
		ans = min(ans, c[0][i - 1] + c[1][i + 2])
	print(ans)


import sys
from collections import defaultdict, Counter, OrderedDict, deque
from heapq import heapify, heappop, heappush

def func():
	n = int(input())
	arr = [0]
	arr += list(map(int, input().split()))
	ans = sys.maxsize
	num = 0
	f_tmp = [0] * (n + 6)
	g_tmp = [0] * (n + 6)
	for i in range(2, n):
		tmp = max(arr[i - 1], arr[i + 1])
		f_tmp[i] = f_tmp[i - 2]
		if tmp >= arr[i]:
			f_tmp[i] += tmp - arr[i] + 1
	for i in range(n - 1, 1, -1):
		tmp = max(arr[i - 1], arr[i + 1])
		g_tmp[i] = g_tmp[i + 2]
		if tmp >= arr[i]:
			g_tmp[i] += tmp - arr[i] + 1
	if n & 1:
		ans = f_tmp[n - 1]
	else:
		ans = min(f_tmp[n - 2], f_tmp[n - 1])
		for i in range(0, n, 2):
			if i + 3 < n:
				ans = min(ans, f_tmp[i] + g_tmp[i + 3])
	print(ans)
tc = int(input())
while tc > 0:
	func()
	tc -= 1


for q in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	lis = [0]
	odd = []
	even = []
	cnta = 0
	cntb = 0
	for i in range(1, n - 1):
		if i % 2:
			if arr[i] > max(arr[i - 1], arr[i + 1]):
				odd.append(0)
				cnta += 1
			else:
				odd.append(max(arr[i + 1], arr[i - 1]) - arr[i] + 1)
		elif arr[i] > max(arr[i - 1], arr[i + 1]):
			even.append(0)
			cntb += 1
		else:
			even.append(max(arr[i + 1], arr[i - 1]) - arr[i] + 1)
	if n % 2:
		print(sum(odd))
		continue
	op = [odd[0]]
	ep = [even[0]]
	for i in range(1, n // 2 - 1):
		op.append(op[-1] + odd[i])
		ep.append(ep[-1] + even[i])
	ans = min(sum(odd), sum(even))
	for i in range(n // 2 - 1):
		ans = min(ans, op[i] + ep[-1] - ep[i])
	print(ans)


from collections import defaultdict
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ld = []
	odd = 0
	even = 0
	lans = []
	for j in range(1, n - 1):
		lv = l[j + 1] - l[j]
		rv = l[j - 1] - l[j]
		if lv < 0:
			lv = -1
		if rv < 0:
			rv = -1
		ld.append(max(lv + 1, rv + 1))
		if j % 2 == 1:
			odd += ld[j - 1]
		else:
			even += ld[j - 1]
	lans.append(even)
	lans.append(odd)
	su = even
	for j in range((n - 2) // 2):
		su = su - ld[2 * j + 1] + ld[2 * j]
		lans.append(su)
	if n % 2 == 0:
		print(min(lans))
	else:
		print(odd)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	ans = 0
	if n % 2 == 1:
		for i in range(1, n, 2):
			ans += max(0, max(h[i - 1], h[i + 1]) + 1 - h[i])
	else:
		a = [0] * n
		b = [0] * n
		for i in range(1, n - 1):
			d = max(0, max(h[i - 1], h[i + 1]) + 1 - h[i])
			if i % 2 == 1:
				a[i] = d
			else:
				b[i] = d
		ans = 10 ** 20
		for i in range(n - 1):
			a[i + 1] += a[i]
		for i in range(n - 1, 0, -1):
			b[i - 1] += b[i]
		for i in range(0, n, 2):
			ans = min(ans, a[i] + b[i + 1])
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	L = list(map(int, input().split()))
	ans1 = 0
	for i in range(1, n - 1, 2):
		ans1 += max(0, max(L[i - 1], L[i + 1]) + 1 - L[i])
	if n % 2 == 1:
		print(ans1)
		continue
	M = []
	for i in range(1, n - 1, 2):
		M.append(max(0, max(L[i - 1], L[i + 1]) + 1 - L[i]))
	N = []
	for i in range(2, n - 1, 2):
		N.append(max(0, max(L[i - 1], L[i + 1]) + 1 - L[i]))
	P1 = [M[0]]
	for i in range(1, len(M)):
		P1.append(P1[-1] + M[i])
	P2 = [N[-1]]
	for i in range(len(N) - 2, -1, -1):
		P2.append(P2[-1] + N[i])
	ans = min(P1[-1], P2[-1])
	j = len(P1)
	for i in range(0, len(P1) - 1):
		ans = min(ans, P1[j - i - 2] + P2[i])
	print(ans)


def cnt(x):
	return max(max(li[x - 1], li[x + 1]) + 1 - li[x], 0)
t = int(input())
for _ in range(t):
	n = int(input())
	li = list(map(int, input().split()))
	ans = 0
	for i in range(1, len(li) - 1, 2):
		ans += cnt(i)
	if n % 2 == 1:
		print(ans)
		continue
	cur = 0
	for i in range(2, len(li) - 1, 2):
		cur += cnt(i)
	ans = min(ans, cur)
	for i in range(2, len(li) - 1, 2):
		cur += cnt(i - 1)
		cur -= cnt(i)
		ans = min(ans, cur)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	h = [*map(int, input().split())]
	if n & 1:
		ans = 0
		for i in range(1, n - 1, 2):
			ans += max(0, max(h[i - 1], h[i + 1]) + 1 - h[i])
		print(ans)
	else:
		ans = [10 ** 9 * 2] * n
		ans[0] = ans[-1] = 0
		for j in range(2):
			for i in range(1 + j, n - 1, 2):
				ans[i] = max(0, max(h[i - 1], h[i + 1]) + 1 - h[i])
		ANS = min(sum(ans[1:-1:2]), sum(ans[2:-1:2]))
		(p, s) = ([0] * n, [0] * n)
		for j in range(2):
			for i in range(1 + j, n - 1, 2):
				p[i] = ans[i] + (p[i - 2] if i >= 2 else 0)
		for j in range(2):
			for i in range(n - 2 - j, 0, -2):
				s[i] = ans[i] + (s[i + 2] if i + 2 < n else 0)
		for i in range(1, n - 4, 2):
			ANS = min(ANS, p[i] + s[i + 3])
		print(ANS)


import sys
t = int(input())
result = []
for _ in range(t):
	n = int(input())
	array = list(map(int, input().split()))

	def solve():
		suffixSum = [float('inf') for i in range(n)]
		suffixSum[n - 2] = max(max(array[n - 1], array[n - 3]) + 1 - array[n - 2], 0)
		if len(suffixSum) > 3:
			suffixSum[n - 3] = max(max(array[n - 4], array[n - 2]) + 1 - array[n - 3], 0)
		for i in reversed(range(1, n - 2)):
			currentMax = max(array[i - 1], array[i + 1]) + 1
			suffixSum[i] = max(currentMax - array[i], 0) + suffixSum[i + 2]
		(currentSum, currentMin) = (0, float('inf'))
		for i in range(1, n - 1, 2):
			if i + 2 < len(array):
				currentMin = min(currentMin, currentSum + suffixSum[i + 1])
			currentMax = max(array[i - 1], array[i + 1]) + 1
			currentSum += max(currentMax - array[i], 0)
		return min(currentMin, currentSum)
	ans = solve()
	print(ans)


def main():
	for t in range(int(input())):
		n = int(input())
		h = list(map(int, input().split()))
		if n % 2 == 1:
			ans = 0
			for i in range(1, n, 2):
				if h[i] > h[i - 1] and h[i] > h[i + 1]:
					continue
				ans += max(h[i - 1], h[i + 1]) + 1 - h[i]
			print(ans)
		else:
			(ans1, ans2) = (0, 0)
			(c1, c2) = ([0 for i in range(n + 1)], [0 for i in range(n + 1)])
			for i in range(1, n - 2, 2):
				if h[i] > h[i - 1] and h[i] > h[i + 1]:
					continue
				ans1 += max(h[i - 1], h[i + 1]) + 1 - h[i]
				c1[i] = max(h[i - 1], h[i + 1]) + 1 - h[i]
			for i in range(2, n - 1, 2):
				if h[i] > h[i - 1] and h[i] > h[i + 1]:
					continue
				ans2 += max(h[i - 1], h[i + 1]) + 1 - h[i]
				c2[i] = max(h[i - 1], h[i + 1]) + 1 - h[i]
			for i in range(1, n):
				c1[i] += c1[i - 1]
				c2[i] += c2[i - 1]
			ans = min(ans1, ans2)
			for i in range(1, n - 2, 2):
				ans = min(ans, c2[n - 1] - c2[i] + c1[i - 1])
			print(ans)
main()


from collections import deque
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	res = 0
	dp = [float('inf')] * n
	for i in range(1, n - 1):
		dp[i] = max(0, 1 + max(arr[i - 1], arr[i + 1]) - arr[i])
	if n % 2:
		for i in range(1, n - 1, 2):
			res += dp[i]
	else:
		(last_odd, last_even) = (0, 0)
		even = deque()
		odd = deque()
		i = 1
		while i < n - 1:
			last_odd += dp[i]
			last_even += dp[i + 1]
			odd.append(last_odd)
			even.append(last_even)
			i += 2
		res = min(odd[-1], even[-1])
		m = (n - 1) // 2
		pos = 0
		for j in range(m):
			res = min(res, odd[pos] + even[-1] - even[pos])
			pos += 1
	print(res)


import sys
inp = sys.stdin.readline
for _ in range(int(inp())):
	n = int(inp())
	h = list(map(int, inp().split()))
	res = 0
	if n % 2 == 1:
		for i in range(1, n - 1, 2):
			a = h[i - 1] - h[i] + 1
			b = h[i + 1] - h[i] + 1
			res += max(0, max(a, b))
	else:
		pref = [0] * n
		suff = [0] * n
		for i in range(1, n - 1):
			a = h[i - 1] - h[i] + 1
			b = h[i + 1] - h[i] + 1
			if i % 2 == 1:
				pref[i] = max(0, max(a, b))
			else:
				suff[i] = max(0, max(a, b))
		for i in range(n - 1):
			pref[i + 1] += pref[i]
			suff[n - 2 - i] += suff[n - i - 1]
		res = pref[0] + suff[1]
		for i in range(0, n, 2):
			res = min(res, pref[i] + suff[i + 1])
	print(res)


for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	x = (n - 1) // 2
	w = []
	for i in range(1, n - 1):
		w += [max(0, max(a[i - 1], a[i + 1]) + 1 - a[i])]
	if n % 2:
		ans = 0
		for i in range(0, n - 2, 2):
			ans += w[i]
		print(ans)
	else:
		m = n - 2
		a1 = 0
		a2 = 0
		for i in range(0, m, 2):
			a1 += w[i]
		for i in range(1, m, 2):
			a2 += w[i]
		if n > 5:
			r = list(w)
			for i in range(m - 3, -1, -1):
				w[i] += w[i + 2]
			x = 0
			for i in range(0, m, 2):
				x += r[i]
				a1 = min(a1, x - r[i] + w[i + 1])
			r = r[::-1]
			k = list(r)
			x = 0
			for i in range(m - 3, -1, -1):
				r[i] += r[i + 2]
			for i in range(0, m, 2):
				x += k[i]
				a2 = min(a2, x - k[i] + r[i + 1])
		print(min(a1, a2))


for tt in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	arr = []
	for i in range(1, n - 1):
		arr += [max(0, max(a[i - 1], a[i + 1]) + 1 - a[i])]
	if n % 2:
		ans = 0
		for i in range(0, n - 2, 2):
			ans += arr[i]
		print(ans)
	else:
		lem = n - 2
		ans1 = sum((arr[i] for i in range(0, lem, 2)))
		ans2 = sum((arr[i] for i in range(1, lem, 2)))
		if n > 5:
			r = list(arr)
			for i in range(lem - 3, -1, -1):
				arr[i] += arr[i + 2]
			x = 0
			for i in range(0, lem, 2):
				x += r[i]
				ans1 = min(ans1, x - r[i] + arr[i + 1])
			r = r[::-1]
			k = list(r)
			for i in range(lem - 3, -1, -1):
				r[i] += r[i + 2]
			x = 0
			for i in range(0, lem, 2):
				x += k[i]
				ans2 = min(ans2, x - k[i] + r[i + 1])
		print(min(ans1, ans2))


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

def f(i, toggle):
	if i >= n - 1:
		return 0
	if dp[i][toggle] != -1:
		return dp[i][toggle]
	k = max(max(a[i - 1], a[i + 1]) - a[i] + 1, 0)
	if toggle:
		dp[i][toggle] = k + f(i + 2, toggle)
		return dp[i][toggle]
	dp[i][toggle] = k + min(f(i + 2, toggle), f(i + 3, 1))
	return dp[i][toggle]

def get(i):
	ans = 0
	for i in range(i, n, 2):
		if i == n - 1:
			continue
		ans += max(max(a[i + 1], a[i - 1]) - a[i] + 1, 0)
	return ans
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	dp = [[-1, -1] for _ in range(n)]
	d = [[0, 0] for _ in range(n + 2)]
	if n % 2 == 0:
		for i in range(n - 2, -0, -1):
			k = max(max(a[i - 1], a[i + 1]) - a[i] + 1, 0)
			d[i][1] = k + d[i + 2][1]
			d[i][0] = k + min(d[i + 2][0], d[i + 3][1])
	if n % 2:
		print(get(1))
	else:
		print(min(d[1][0], d[1][1], get(2)))


T = int(input())
for t in range(T):
	n = int(input())
	in_data = list(map(int, input().split()))
	dp = [[10 ** 18 for i in range(n + 1)], [10 ** 18 for i in range(n + 1)]]
	dp[0][1] = 0
	for i in range(1, n - 1):
		for j in range(2):
			if j == 0:
				dp[1][i + 1] = min(dp[1][i + 1], dp[0][i])
				gr = max(0, max(in_data[i - 1] - in_data[i] + 1, in_data[i + 1] - in_data[i] + 1))
				dp[0][i + 2] = min(dp[0][i + 2], dp[0][i] + gr)
			else:
				gr = max(0, max(in_data[i - 1] - in_data[i] + 1, in_data[i + 1] - in_data[i] + 1))
				dp[1][i + 2] = min(dp[1][i + 2], dp[1][i] + gr)
	if len(in_data) % 2 == 1:
		print(dp[0][n])
	else:
		print(min(dp[0][n - 1], dp[1][n]))