Suppose we have a 2D grid $A$ of infinite width and height of $N$ units. Each row of the grid can be represented in the form of $111\ldots100\ldots \infty$ where the $1$s are repeated $x$ times, $x > 0$. Implying that the row starts with $x$ consecutive $1$-s followed by all $0$-s. 

Initially all cells are unmarked. Cell (i,j) refers to the i-th row, and j-th column. (1,1) refers to the bottom-left cell.

Now you do the following in each step.

Choose an unmarked cell having 1. Let it be (i, j).
while((i,j) lies in the grid boundaries && A[i][j] == 1){
	mark[i][j] = true; i--; j--;
}

How many minimum number of steps are required to mark all the cells containing $1$?

Note: The number of consecutive $1$-s at each height is given by the array $W$ where $W_{i}$ represents the same at $i^{th}$ row.

------ Input: ------
First line will contain $T$, number of testcases. Then the testcases follow. 
Each testcase contain $2$ lines of input.
First line will contain $N$, height of the grid (number of rows). 
Second line contains $N$ space separated integers where $i^{th}$ index represents number of consecutive $1$-s at the beginning of row $i$.

------ Output: ------
For each testcase, output in a single line answer to the problem.

------ Constraints  ------
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$1 ≤ W_{i} ≤ 10^{9}$

----- Sample Input 1 ------ 
3
3
1 1 1
3
5 3 2
3
4 2 5
----- Sample Output 1 ------ 
3
7
8
----- explanation 1 ------ 
TestCase 1: All the points need to be considered to cover all $1$-s.

TestCase 2: The optimal set of starting points is $\{(1, 3), (2, 3), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1)\}$.

![fig1]

Difficulty: HARD

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	(init, *w) = [int(x) for x in input().split()]
	min_ = 0
	max_ = init
	count = 0
	for (i, x) in enumerate(w):
		minv = -(i + 1)
		maxv = x - (i + 1)
		count += min(max_, minv) - min(min_, minv)
		count += max(max_, maxv) - max(min_, maxv)
		min_ = minv
		max_ = maxv
	print(count + (max_ - min_))


for t in range(int(input())):
	n = int(input())
	grid = [int(i) for i in input().split()][::-1]
	tocount = grid[:1] + [0 if grid[i + 1] - grid[i] + 1 < 1 else grid[i + 1] - grid[i] + 1 for i in range(n - 1)]
	print(sum(tocount))


def solution():
	t = int(input())
	for _ in range(t):
		n = int(input())
		li = [int(i) for i in input().split(' ')][::-1]
		count = 0
		maxx = 1
		i = 0
		while i < n:
			if li[i] > maxx - 1:
				count += li[i] - (maxx - 1)
			maxx = li[i]
			i += 1
		print(count)
solution()


import sys
from math import sqrt, gcd
from collections import deque, Counter, OrderedDict
input = lambda : sys.stdin.readline()
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 1000000007
for _ in range(I()):
	n = I()
	w = L()[::-1]
	ans = w[0]
	for i in range(1, n):
		if w[i] > w[i - 1] - 1:
			ans += w[i] - w[i - 1] + 1
	print(ans)


t = int(input())
for z in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	c = 0
	c = c + arr[n - 1]
	for i in range(n - 2, -1, -1):
		if arr[i] >= arr[i + 1]:
			x = arr[i] - arr[i + 1] + 1
			c = c + x
	print(c)


t = int(input())
for _ in range(t):
	N = int(input())
	st = input().split()
	dx = 0
	mx = 1
	r = 0
	for x in st:
		n = int(x) - dx
		r += 1
		if n > mx:
			r += n - mx
		mx = n
		dx += 1
	print(r)


try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		l = list(map(int, input().split()))
		l = l[::-1]
		res = l[0]
		for i in range(1, n):
			if l[i] >= l[i - 1]:
				res += l[i] - l[i - 1] + 1
		print(res)
except:
	pass


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


for _ in range(int(input())):
	n = input()
	l = list(map(int, input().split()))
	p = c = l[len(l) - 1]
	for i in range(len(l) - 2, -1, -1):
		if l[i] >= p:
			c += l[i] - p + 1
		p = l[i]
	print(c)


for i in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	cnt = ls[-1]
	for i in range(n - 1):
		if ls[i + 1] <= ls[i]:
			cnt += ls[i] - ls[i + 1] + 1
	print(cnt)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		if i == n - 1:
			req = 0
		elif arr[i] < arr[i + 1]:
			req = arr[i]
		else:
			req = arr[i + 1] - 1
		ans = ans + (arr[i] - req)
	print(ans)


for i in range(int(input())):
	n = int(input())
	t = [int(x) for x in input().split()]
	s = t[len(t) - 1]
	for j in range(len(t) - 2, -1, -1):
		if t[j] > t[j + 1] - 1:
			s = s + t[j] - t[j + 1] + 1
	print(s)


T = int(input())
ans = []
for _ in range(T):
	N = int(input())
	A = [int(i) for i in input().split()]
	diff = 0
	for i in range(N - 1, 0, -1):
		if A[i] > A[i - 1]:
			diff += A[i] - A[i - 1] - 1
	ans.append(N + A[0] - 1 + diff)
for i in ans:
	print(i)


t = int(input())
for l in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	count = arr[n - 1]
	for i in range(n - 2, -1, -1):
		s = arr[i] - arr[i + 1] + 1
		if s >= 1:
			count += s
	print(count)


try:
	for t in range(int(input())):
		n = int(input())
		ls = list(map(int, input().split()))
		ls[:] = ls[::-1]
		c = ls[0]
		for i in range(1, len(ls)):
			if ls[i] >= ls[i - 1]:
				c += ls[i] - (ls[i - 1] - 1)
		print(c)
except:
	pass


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = a[-1]
	for i in range(n - 2, -1, -1):
		ma = a[i + 1] - 1
		if a[i] <= ma:
			continue
		ans += a[i] - ma
	print(ans)


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


t = int(input())
for z in range(0, t):
	n = int(input())
	arr = list(map(int, input().split()))
	count = 0
	for i in range(n - 1, -1, -1):
		if i == n - 1:
			count += arr[i]
			continue
		if arr[i] < arr[i + 1]:
			continue
		else:
			count += arr[i] - (arr[i + 1] - 1)
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	w = list(map(int, input().split()))
	a = w[n - 1]
	i = n - 2
	while i >= 0:
		b = w[i + 1] - 1
		if w[i] <= b:
			i -= 1
			continue
		a += w[i] - b
		i -= 1
	print(a)


testcases = int(input())
for i in range(0, testcases):
	height = int(input())
	onesrow = list(map(int, input().split()))
	onesrow.reverse()
	steps = onesrow[0]
	cross = steps - 1
	for one in onesrow[1:]:
		if cross < one:
			steps += one - cross
		cross = one - 1
	print(steps)


t = int(input())
for y in range(t):
	n = int(input())
	w = list(map(int, input().split()))
	k = n - 1
	c = 0
	p = 0
	for i in range(n):
		o = w[k]
		if p == 0:
			c = c + o
		elif o >= p:
			c = c + (o - p + 1)
		k = k - 1
		p = o
	print(c)


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = arr[-1]
	for i in range(n - 2, -1, -1):
		if arr[i] >= arr[i + 1]:
			ans += arr[i] - arr[i + 1] + 1
	print(ans)


for __ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	s = sum(arr)
	for i in range(n - 1):
		s -= min(arr[i], arr[i + 1] - 1)
	print(s)


for j in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	strt = []
	for i in range(n - 1):
		if a[i + 1] <= a[i]:
			strt.append(a[i] - a[i + 1] + 1)
		else:
			strt.append(0)
	strt.append(a.pop())
	print(sum(strt))


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		print(arr[0])
		continue
	arr = arr[::-1]
	sum = arr[0]
	for i in range(1, len(arr)):
		if arr[i] > arr[i - 1] - 1:
			sum += arr[i] + 1 - arr[i - 1]
	print(sum)


i = int(input())
for _ in range(i):
	n = int(input())
	w = list(map(int, input().split()))
	steps = w[-1]
	for j in range(n - 1):
		if w[j + 1] <= w[j]:
			steps += w[j] - w[j + 1] + 1
	print(steps)


t = int(input())
for i in range(0, t):
	N = int(input())
	st = input()
	arr = list(map(int, st.split(' ')))
	op = 0
	for j in range(0, len(arr) - 1):
		if arr[j] >= arr[j + 1]:
			op = op + arr[j] - arr[j + 1] + 1
	print(op + arr[N - 1])


for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	count = w[n - 1]
	n -= 2
	while n >= 0:
		maxi = w[n + 1] - 1
		if maxi < w[n]:
			count += w[n] - maxi
		n -= 1
	print(count)


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

def getIntArray():
	return list(getIntList())

def getInt():
	return int(input())
for _ in range(int(input())):
	n = getInt()
	a = getIntArray()[::-1]
	c = a[0]
	for (i, v) in enumerate(a[1:]):
		c += max(0, v - a[i] + 1)
	print(c)


try:
	for t in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		dp = arr[-1]
		for i in range(n - 2, -1, -1):
			m = arr[i + 1] - 1
			if arr[i] <= m:
				continue
			dp += arr[i] - m
		print(dp)
except:
	pass


for ttt in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = arr[n - 1]
	for i in range(n - 2, -1, -1):
		if arr[i] <= arr[i + 1] - 1:
			pass
		else:
			ans += arr[i] - (arr[i + 1] - 1)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	count = l[n - 1]
	for i in range(len(l) - 2, -1, -1):
		ma = l[i + 1] - 1
		if l[i] <= ma:
			continue
		count += l[i] - ma
	print(count)


def solve(N, arr):
	if N == 1:
		return arr[0]
	else:
		ans = arr[0]
		for i in range(1, len(arr)):
			prev = min(arr[i - 1] - 1, arr[i])
			ans += arr[i] - prev
		return ans
for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().rstrip().split(' ')]
	arr.reverse()
	print(solve(n, arr))


from collections import defaultdict as dd
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	s = 0
	ans = 0
	for i in range(n - 1, -1, -1):
		ans += max(0, w[i] - s)
		s = w[i] - 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	ip = input()
	temp = ip.split()
	listA = []
	for i in range(len(temp)):
		ele = int(temp[i])
		listA.append(ele)
	su_m = 0
	for i in range(n):
		if i == 0:
			su_m = su_m + listA[n - 1 - i]
		elif listA[n - i] > listA[n - i - 1] + 1:
			continue
		else:
			su_m = su_m + listA[n - i - 1] + 1 - listA[n - i]
	print(su_m)


for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	steps = arr[n - 1]
	for i in range(n - 1, 0, -1):
		if arr[i] <= arr[i - 1]:
			steps = steps + arr[i - 1] - arr[i] + 1
	print(steps)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	count = arr[-1]
	i = n - 2
	while i >= 0:
		if arr[i] >= arr[i + 1]:
			count += arr[i] - (arr[i + 1] - 1)
		i -= 1
	print(count)


for t in range(int(input())):
	h = int(input())
	x = list(map(int, input().split(' ')))
	x.reverse()
	distinctMarking = 0
	for i in range(len(x)):
		if i == 0:
			distinctMarking += x[i]
		elif x[i] >= x[i - 1]:
			distinctMarking += x[i] - x[i - 1] + 1
	print(distinctMarking)


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


from sys import stdin, stdout
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import *
from random import *
input = stdin.readline
prin = stdout.write
from random import sample
from collections import Counter, deque
from math import sqrt, ceil, log2, gcd
mod = 10 ** 9 + 7

def f(arr, i, j, d, dist):
	if i == j:
		return
	nn = max(arr[i:j])
	for tl in range(i, j):
		if arr[tl] == nn:
			dist[tl] = d
			f(arr, i, tl, d + 1, dist)
			f(arr, tl + 1, j, d + 1, dist)

def ps(n):
	cp = 0
	lk = 0
	arr = {}
	cc = 0
	ans = 1
	while n % 2 == 0:
		n = n // 2
		lk += 1
		cc = 1
	if lk % 2 == 1:
		ans *= 2
	for ps in range(3, ceil(sqrt(n)) + 1, 2):
		lk = 0
		cc = 0
		while n % ps == 0:
			n = n // ps
			cc = 1
			lk += 1
		if lk % 2 == 1:
			ans *= ps
	if n != 1:
		ans *= n
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def factorials(n, r):
	slr = n
	dpr = r
	qlr = 1
	qs = 1
	mod = 10 ** 9 + 7
	for ip in range(n - r + 1, n + 1):
		qlr = qlr * ip % mod
	for ij in range(1, r + 1):
		qs = qs * ij % mod
	ans = qlr * modInverse(qs) % mod
	return ans

def modInverse(b):
	qr = 10 ** 9 + 7
	return pow(b, qr - 2, qr)
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def power(arr):
	listrep = arr
	subsets = []
	for i in range(2 ** len(listrep)):
		subset = []
		for k in range(len(listrep)):
			if i & 1 << k:
				subset.append(listrep[k])
		subsets.append(subset)
	return subsets

def pda(n):
	list = []
	for i in range(1, int(sqrt(n) + 1)):
		if n % i == 0:
			if n // i == i:
				list.append(i)
			else:
				list.append(n // i)
				list.append(i)
	return list

def dis(xa, ya, xb, yb):
	return sqrt((xa - xb) ** 2 + (ya - yb) ** 2)

def ii():
	return int(input())

def ilist():
	return [int(x) for x in input().strip().split()]

def islist():
	return list(map(str, input().split().rstrip()))

def inp():
	return input().strip()

def google(test, ans):
	return 'Case #' + str(test) + ': ' + str(ans)

def overlap(x1, y1, x2, y2):
	if x2 > y1:
		return y1 - x2
	if y1 > y2:
		return y2 - x2
	return y1 - x2
t = int(input())
for p in range(t):
	n = ii()
	w = ilist()[::-1]
	ans = w[0]
	for i in range(1, n):
		ans += max(0, w[i] + 1 - w[i - 1])
	print(ans)


t = int(input())
while t != 0:
	n = int(input())
	l = list(map(int, input().split()))
	c = l[n - 1]
	for i in range(n - 2, -1, -1):
		if l[i + 1] <= l[i]:
			c += l[i] - l[i + 1] + 1
	print(c)
	t -= 1


for _ in range(int(input())):
	N = int(input())
	cols = [int(x) for x in input().split()]
	ans = cols[-1]
	for i in reversed(range(0, N - 1)):
		maxi = cols[i + 1] - 1
		if cols[i] <= maxi:
			continue
		ans += cols[i] - maxi
	print(ans)


for t in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	l.reverse()
	loops = l[0]
	cur = l[0] - 1
	for i in range(1, n):
		if cur >= l[i]:
			cur = l[i] - 1
		elif cur < l[i] and cur != 0:
			ncur = l[i] - cur
			cur = l[i] - 1
			loops += ncur
		else:
			loops += l[i]
			cur = l[i] - 1
	print(loops)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.reverse()
	c = l[0]
	for j in range(1, len(l)):
		if l[j] >= l[j - 1]:
			c += l[j] - l[j - 1] + 1
	print(c)


t = int(input())
while t:
	t -= 1
	n = int(input())
	arr = list(map(int, input().split()))
	p = 0
	final = 0
	for i in range(len(arr) - 1, -1, -1):
		if arr[i] > p:
			final += arr[i] - p
			p = arr[i] - 1
		else:
			p = min(arr[i], p) - 1
	print(final)


def answer():
	(ans, v) = (0, 0)
	for i in a[::-1]:
		ans += max(0, i - v)
		v = i - 1
	return ans
for T in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(answer())


t = int(input())
for _ in range(t):
	n = int(input())
	h = [int(s) for s in input().split()]
	h_pom = [0 for _ in range(n)]
	res = sum(h)
	for i in range(n - 1, 0, -1):
		num = min(max(0, h[i] - 1), h[i - 1])
		h_pom[i - 1] += num
		res -= num
	print(res)


t = int(input())
for i in range(t):
	n = int(input())
	A = [int(j) for j in input().split()]
	j = 0
	out = 0
	while j < n - 1:
		if A[j] - (A[j + 1] - 1) >= 0:
			out = out + A[j] - (A[j + 1] - 1)
		j += 1
	print(out + A[n - 1])


t = int(input())
while t:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))[::-1]
	ans = l[0]
	for i in range(1, n):
		ans = ans + l[i] - min(l[i - 1] - 1, l[i])
	print(ans)


t = int(input())
while t:
	n = int(input())
	ncons = list(map(int, input().split()))
	num = ncons[-1]
	for i in range(len(ncons) - 2, -1, -1):
		if ncons[i] >= ncons[i + 1]:
			num += ncons[i] - ncons[i + 1] + 1
	print(num)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	ones = list(map(int, input().split()))
	steps = ones[n - 1]
	for i in range(n - 2, -1, -1):
		if ones[i] >= ones[i + 1]:
			steps += ones[i] - ones[i + 1] + 1
	print(steps)


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


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	l1 = [int(i) for i in input().split(' ')]
	ans = sum(l1)
	for i in range(n - 1, 0, -1):
		ans -= min(l1[i] - 1, l1[i - 1])
	print(ans)


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


def solve(w, n):
	ans = w[-1]
	for i in range(n - 1, 0, -1):
		ans += max(0, w[i - 1] - w[i] + 1)
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	w = list(map(int, input().split()))
	print(solve(w, n))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.reverse()
	tmp = [1, a[0]]
	ans = [1]
	for i in range(1, n):
		x = i + 1 + a[i]
		if x == tmp[0] + tmp[1]:
			continue
		elif x < tmp[0] + tmp[1]:
			if len(ans) != 1:
				ans.append(tmp[1] - a[i] - 1 + 1)
			else:
				ans.append(tmp[1] - a[i] - 1)
			tmp = [i + 1, a[i]]
		elif x > tmp[0] + tmp[1]:
			if len(ans) == 1:
				ans.append(0)
			elif tmp[1] - (a[i] - (a[i] + i + 1 - sum(tmp))) > 0:
				ans.append(tmp[1] - (a[i] - (a[i] + i + 1 - sum(tmp))))
			else:
				ans.append(tmp[1])
			tmp = [i + 1, a[i]]
	if len(ans) == 1:
		print(a[0])
	elif len(ans) == 2:
		print(sum(ans) + sum(tmp))
	else:
		print(sum(ans) + tmp[1])


t = int(input())
for _ in range(t):
	n = int(input())
	w = [int(i) for i in input().split(' ')]
	c = w[n - 1]
	for i in range(n - 2, -1, -1):
		c = c + max(0, w[i] - w[i + 1] + 1)
	print(c)


def point(w, n):
	p = 0
	for i in w:
		p = p + i
	s = 0
	for i in range(n - 1):
		if w[i] >= w[i + 1]:
			s += w[i + 1] - 1
		elif w[i] < w[i + 1]:
			s += w[i]
	return p - s
t = int(input())
for _ in range(t):
	n = int(input())
	w = list(map(int, input().split()))
	print(point(w, n))


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


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


T = int(input())
for _ in range(T):
	n = int(input())
	w = list(map(int, input().split()))
	s = 0
	for i in range(n - 1):
		if w[i] >= w[i + 1]:
			s += w[i] - w[i + 1] + 1
	s += w[n - 1]
	print(s)


def foo(n, k):
	my_sum = 0
	last = 0
	for i in range(n):
		if i == 0:
			my_sum = k[n - 1]
		else:
			curr = k[n - i - 1]
			prev = k[n - i]
			covered = min(prev - 1, k[n - i - 1])
			my_sum += k[n - 1 - i] - covered
	return my_sum
t = int(input())
for i in range(t):
	n = int(input())
	k = [int(x) for x in input().split()]
	print(foo(n, k))


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	count = arr[-1]
	for i in range(n - 2, -1, -1):
		if arr[i] >= arr[i + 1]:
			count += arr[i] - arr[i + 1] + 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	c = 0
	for i in range(1, len(w)):
		if w[i - 1] >= w[i]:
			c += w[i - 1] - w[i] + 1
	print(c + w[n - 1])


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


t = int(input())
for i in range(0, t):
	n = int(input())
	lst = list(map(int, input().split()))
	start = lst[0]
	value = start
	for i in range(1, len(lst)):
		if start >= lst[i]:
			value += 1
		elif start < lst[i]:
			value += lst[i] - start
		start = lst[i]
	print(value)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ops = 0
	c = 0
	for i in range(n - 1, -1, -1):
		if arr[i] > c:
			ops = ops + arr[i] - c
		c = arr[i] - 1
	print(ops)


T = int(input())
for i in range(T):
	N = int(input())
	line = input()
	W = [int(x) for x in line.split()]
	count = W[0]
	for j in range(1, N):
		count = count + max(1, W[j] - W[j - 1])
	print(count)


for i in range(int(input())):
	n = int(input())
	ls = [int(x) for x in input().split()]
	ls.reverse()
	s = ls[0]
	for j in range(1, n):
		if ls[j] > ls[j - 1] - 1:
			s += ls[j] - ls[j - 1] + 1
	print(s)


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


def solve():
	N = int(input())
	w = [int(x) for x in input().split()]
	max_val = w[0] - 1
	count = w[0] + N - 1
	for i in range(N):
		if w[i] - i - 1 > max_val:
			count += w[i] - i - 1 - max_val
		max_val = w[i] - i - 1
	print(count)

def main():
	tc = int(input())
	while tc > 0:
		solve()
		tc -= 1
main()


def sol():
	import math
	n = int(input())
	w = list(map(int, input().split()))
	count = 0
	for i in range(n - 1):
		if w[i + 1] <= w[i]:
			count += w[i] - w[i + 1] + 1
		elif w[i + 1] > w[i]:
			pass
	count += w[-1]
	return count
tests = int(input())
for _ in range(tests):
	print(sol())


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


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


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = a[n - 1]
	t = a[n - 1]
	for i in range(n - 2, -1, -1):
		if t - 1 < a[i]:
			cnt += a[i] - (t - 1)
		t = a[i]
	print(cnt)