There is a trampoline park with $n$ trampolines in a line. The $i$-th of which has strength $S_i$.

Pekora can jump on trampolines in multiple passes. She starts the pass by jumping on any trampoline of her choice.

If at the moment Pekora jumps on trampoline $i$, the trampoline will launch her to position $i + S_i$, and $S_i$ will become equal to $\max(S_i-1,1)$. In other words, $S_i$ will decrease by $1$, except of the case $S_i=1$, when $S_i$ will remain equal to $1$.

If there is no trampoline in position $i + S_i$, then this pass is over. Otherwise, Pekora will continue the pass by jumping from the trampoline at position $i + S_i$ by the same rule as above.

Pekora can't stop jumping during the pass until she lands at the position larger than $n$ (in which there is no trampoline). Poor Pekora!

Pekora is a naughty rabbit and wants to ruin the trampoline park by reducing all $S_i$ to $1$. What is the minimum number of passes she needs to reduce all $S_i$ to $1$?


-----Input-----

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

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 5000$) — the number of trampolines.

The second line of each test case contains $n$ integers $S_1, S_2, \dots, S_n$ ($1 \le S_i \le 10^9$), where $S_i$ is the strength of the $i$-th trampoline.

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


-----Output-----

For each test case, output a single integer — the minimum number of passes Pekora needs to do to reduce all $S_i$ to $1$.


-----Examples-----

Input
3
7
1 4 2 2 2 2 2
2
2 3
5
1 1 1 1 1
Output
4
3
0


-----Note-----

For the first test case, here is an optimal series of passes Pekora can take. (The bolded numbers are the positions that Pekora jumps into during these passes.)

$[1,4,\textbf{2},2,\textbf{2},2,\textbf{2}]$

$[1,\textbf{4},1,2,1,\textbf{2},1]$

$[1,\textbf{3},1,2,\textbf{1},\textbf{1},\textbf{1}]$

$[1,\textbf{2},1,\textbf{2},1,\textbf{1},\textbf{1}]$

For the second test case, the optimal series of passes is show below.

$[\textbf{2},3]$

$[1,\textbf{3}]$

$[1,\textbf{2}]$

For the third test case, all $S_i$ are already equal to $1$.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Implementation

Greedy algorithms

Complete search

Dynamic programming

Data structures


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


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
input = lambda : sys.stdin.readline().rstrip()
import bisect, string, math, time, functools, random, fractions
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
from itertools import permutations, combinations, groupby
rep = range
R = range

def I():
	return int(input())

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def AI():
	return map(int, open(0).read().split())

def S_():
	return input()

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

def LS():
	return [i for i in input().split()]

def NI(n):
	return [int(input()) for i in range(n)]

def NI_(n):
	return [int(input()) - 1 for i in range(n)]

def NLI(n):
	return [[int(i) for i in input().split()] for i in range(n)]

def NLI_(n):
	return [[int(i) - 1 for i in input().split()] for i in range(n)]

def StoLI():
	return [ord(i) - 97 for i in input()]

def ItoS(n):
	return chr(n + 97)

def LtoS(ls):
	return ''.join([chr(i + 97) for i in ls])

def RLI(n=8, a=1, b=10):
	return [random.randint(a, b) for i in range(n)]

def RI(a=1, b=10):
	return random.randint(a, b)

def INP():
	N = 100
	n = random.randint(1, N)
	a = RLI(n, 1, 100)
	return [a]

def Rtest(T):
	(case, err) = (0, 0)
	for i in range(T):
		inp = INP()
		a1 = naive(*inp)
		a2 = solve(*inp)
		if a1 != a2:
			print(*inp)
			print('naive', a1)
			print('solve', a2)
			err += 1
		case += 1
	print('Tested', case, 'case with', err, 'errors')

def GI(V, E, ls=None, Directed=False, index=1):
	org_inp = []
	g = [[] for i in range(V)]
	FromStdin = True if ls == None else False
	for i in range(E):
		if FromStdin:
			inp = LI()
			org_inp.append(inp)
		else:
			inp = ls[i]
		if len(inp) == 2:
			(a, b) = inp
			c = 1
		else:
			(a, b, c) = inp
		if index == 1:
			a -= 1
			b -= 1
		aa = (a, c)
		bb = (b, c)
		g[a].append(bb)
		if not Directed:
			g[b].append(aa)
	return (g, org_inp)

def GGI(h, w, search=None, replacement_of_found='.', mp_def={'#': 1, '.': 0}, boundary=1):
	mp = [boundary] * (w + 2)
	found = {}
	for i in R(h):
		s = input()
		for char in search:
			if char in s:
				found[char] = (i + 1) * (w + 2) + s.index(char) + 1
				mp_def[char] = mp_def[replacement_of_found]
		mp += [boundary] + [mp_def[j] for j in s] + [boundary]
	mp += [boundary] * (w + 2)
	return (h + 2, w + 2, mp, found)

def TI(n):
	return GI(n, n - 1)

def accum(ls):
	rt = [0]
	for i in ls:
		rt += [rt[-1] + i]
	return rt

def bit_combination(n, base=2):
	rt = []
	for tb in R(base ** n):
		s = [tb // base ** bt % base for bt in R(n)]
		rt += [s]
	return rt

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

def YN(x):
	print(['NO', 'YES'][x])

def Yn(x):
	print(['No', 'Yes'][x])

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
mo = 10 ** 9 + 7
inf = float('inf')
FourNb = [(-1, 0), (1, 0), (0, 1), (0, -1)]
EightNb = [(-1, 0), (1, 0), (0, 1), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]
compas = dict(zip('WENS', FourNb))
cursol = dict(zip('LRUD', FourNb))
alp = [chr(ord('a') + i) for i in range(26)]
show_flg = False
show_flg = True

def primeFactor(N):
	(i, n) = (2, N)
	ret = {}
	(d, sq) = (2, 99)
	while i <= sq:
		k = 0
		while n % i == 0:
			(n, k, ret[i]) = (n // i, k + 1, k + 1)
		if k > 0 or i == 97:
			sq = int(n ** (1 / 2) + 0.5)
		if i < 4:
			i = i * 2 - 1
		else:
			(i, d) = (i + d, d ^ 6)
	if n > 1:
		ret[n] = 1
	return ret

def divisor(n):
	div = [1]
	for (i, j) in primeFactor(n).items():
		div = [i ** k * d for d in div for k in range(j + 1)]
	return div

def PrimeNumSet(N):
	M = int(N ** 0.5)
	seachList = [i for i in range(2, N + 1)]
	primes = []
	while seachList:
		if seachList[0] > M:
			break
		primes.append(seachList[0])
		tmp = seachList[0]
		seachList = [i for i in seachList if i % tmp != 0]
	return primes + seachList

def LCM(b, mo=10 ** 9 + 7):
	prs = PrimeNumSet(max(b))
	M = dict(zip(prs, [0] * len(prs)))
	for i in b:
		dc = primeFactor(i)
		for (j, k) in dc.items():
			M[j] = max(M[j], k)
	r = 1
	for (j, k) in M.items():
		if k != 0:
			r *= pow(j, k, mo)
			r %= mo
	return r

def extgcd(x, y):
	if y == 0:
		return (1, 0)
	(r0, r1, s0, s1) = (x, y, 1, 0)
	while r1 != 0:
		(r0, r1, s0, s1) = (r1, r0 % r1, s1, s0 - r0 // r1 * s1)
	return (s0, (r0 - s0 * x) // y, x * s0 + y * (r0 - s0 * x) // y)

def crt(rems, mods):
	n = len(rems)
	if n != len(mods):
		return NotImplemented
	(x, d) = (0, 1)
	for (r, m) in zip(rems, mods):
		(a, b, g) = extgcd(d, m)
		(x, d) = ((m * b * x + d * a * r) // g, d * (m // g))
		x %= d
		if r != x % m:
			return (-1, d)
	return (x, d)

def intsqrt(x):
	if x < 0:
		return NotImplemented
	rt = int(x ** 0.5) - 1
	while (rt + 1) ** 2 <= x:
		rt += 1
	return rt
ans = 0

def naive(b):
	a = b[:]
	n = len(a)
	rt = 0
	for i in range(n):
		if a[i] == 1:
			continue
		if a[i] >= n - i:
			rt += a[i] - (n - i)
			a[i] = n - i
		Z = a[i]
		for x in range(Z, 1, -1):
			j = x + i
			rt += 1
			while j < n:
				nx = j + a[j]
				if a[j] > 1:
					a[j] -= 1
				j = nx
	return rt

def solve(b):
	a = b[:]
	n = len(a)
	d = [0] * (n + 1)
	rt = 0
	k = 0
	for i in range(n):
		x = d[i] + k
		c = a[i]
		rt += max(c - 1 - x, 0)
		if c > 1:
			d[min(i + 2, n)] += 1
			d[min(i + c + 1, n)] += -1
		k = max(0, x - (c - 1))
		d[i + 1] += d[i]
	return rt
for _ in range(I()):
	n = I()
	a = LI()
	print(solve(a))


from sys import stdin, stdout
import heapq
from collections import defaultdict
import math
import bisect
import os

def main():
	t = int(stdin.readline())
	for _ in range(t):
		n = int(stdin.readline())
		arr = list(map(int, stdin.readline().split()))
		cur = 0
		dp_plus = [0 for _ in range(n)]
		dp_minus = [0 for _ in range(n)]
		ans = 0
		for (i, x) in enumerate(arr):
			cur += dp_minus[i]
			if cur == 0 and x == 1:
				cur += dp_plus[i]
				continue
			bt = x + cur - 1
			if bt > 0:
				ans += bt
				if i + 2 < n:
					dp_minus[i + 2] -= 1
			else:
				if x >= 2 and i + 2 < n:
					dp_minus[i + 2] -= 1
				if bt < 0 and i + 1 < n:
					dp_minus[i + 1] += bt
					dp_plus[i + 1] -= bt
			if i + x < n and (not (x == 1 and bt < 0)):
				dp_plus[i + x] += 1
			cur += dp_plus[i]
		stdout.write(str(ans) + '\n')
main()


def main():
	import sys
	input = sys.stdin.buffer.readline
	import heapq
	t = int(input())
	ans = []
	for _ in range(t):
		n = int(input())
		S = list(map(int, input().split()))
		q = []
		C = 0
		p = 0
		tmp = S[0] - 1
		for i in range(1, n):
			while q and q[0] < i:
				heapq.heappop(q)
				C -= 1
			if S[i] > C + p:
				tmp += S[i] - 1 - (C + p)
				p = 0
			else:
				p = C + p + 1 - S[i]
			heapq.heappush(q, i + S[i - 1] - 1)
			C += 1
		ans.append(tmp)
	print('\n'.join(map(str, ans)))
main()


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


from sys import stdin
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	s = [int(x) for x in input().split()]
	a = [0] * (n + 1)
	b = []
	ans = 0
	for i in range(n):
		b.append(s[i] - 1 - a[i])
		if s[i] - 1 - a[i] < 0:
			a[i + 1] += abs(s[i] - 1 - a[i])
		else:
			ans += s[i] - 1 - a[i]
		for j in range(2, s[i] + 1):
			if i + j >= n:
				break
			a[i + j] += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	g = [0] * (n + 5)
	las = 0
	for i in range(n):
		tmp = g[i] + las
		las = tmp
		if tmp > a[i] - 1:
			g[i + 1] += tmp - a[i] + 1
			g[i + 2] -= tmp - a[i] + 1
		else:
			ans += a[i] - 1 - tmp
		if i + 2 <= min(n - 1, i + a[i]):
			g[i + 2] += 1
			g[min(n - 1, i + a[i]) + 1] -= 1
	print(ans)


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=2 ** 51, func=lambda a, b: a & b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=10 ** 11, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
for ik in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	l1 = [0] * (n + 1)
	for i in range(n):
		if l1[i] > l[i] - 1:
			l1[i + 1] += l1[i] - (l[i] - 1)
		ans += max(0, l[i] - l1[i] - 1)
		for j in range(i + 2, min(n, i + l[i] + 1)):
			l1[j] += 1
	print(ans)


import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	dp = [0] * n
	ans = 0
	for i in range(n):
		if a[i] > 1:
			for j in range(i + 2, min(i + 1 + a[i], n)):
				dp[j] += 1
		if a[i] - dp[i] > 1:
			ans += a[i] - dp[i] - 1
		elif a[i] - dp[i] < 1:
			if i < n - 1:
				dp[i + 1] += dp[i] - a[i] + 1
	print(ans)


def read_list() -> list:
	return [int(i) for i in input().strip().split()]

def read_num() -> int:
	return int(input().strip())
t = read_num()
for _ in range(t):
	n = read_num()
	arr = read_list()
	ans = 0
	cnt_change = [0] * (n + 5)
	cnt = 0
	for i in range(n):
		cnt += cnt_change[i]
		ans += max(arr[i] - 1 - cnt, 0)
		cnt_change[i + 2] += 1
		cnt_change[min(n - 1, i + arr[i]) + 1] -= 1
		tmp = max(cnt - arr[i] + 1, 0)
		cnt_change[i + 1] += tmp
		cnt_change[i + 2] -= tmp
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	d = 0
	debt = 0
	k = 0
	kmap = dict()
	for i in range(n):
		k -= kmap.get(i, 0)
		d += max(s[i] - (debt + k), 0)
		debt = max(debt + k - s[i], 0)
		k += 1
		kmap[i + s[i] + 1] = kmap.get(i + s[i] + 1, 0) + 1
	print(d - 1)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict

def main():
	for j in range(int(input())):
		n = int(input())
		vals = list(map(int, input().split()))
		ans = 0
		dict1 = defaultdict(int)
		for s in range(n):
			ans += max(vals[s] - 1 - dict1[s], 0)
			for i in range(2, min(vals[s], n - 1 - s) + 1):
				dict1[s + i] += 1
			dict1[s] = max(0, dict1[s] - (vals[s] - 1))
			if s < n - 1:
				dict1[s + 1] += dict1[s]
		print(ans)
main()


from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	pre = [0 for i in range(n)]
	ans = 0
	for i in range(n):
		jumps = [0 for j in range(n)]
		jumps[0] = pre[0]
		for j in range(1, n):
			jumps[j] = jumps[j - 1] + pre[j]
		if a[i]:
			prev_jumps = jumps[i]
			ans += max(0, a[i] - 1 - prev_jumps)
			all = prev_jumps + max(0, a[i] - 1 - prev_jumps)
			if all > a[i] - 1:
				extra = all - (a[i] - 1)
				if i + 1 < n:
					pre[i + 1] += extra
				if i + 2 < n:
					pre[i + 2] -= extra
			start = i + 2
			if start < n:
				pre[start] += 1
				end = min(i + a[i], n - 1)
				if end + 1 < n:
					pre[end + 1] -= 1
	print(ans)


import sys
import math
input = sys.stdin.readline
t = int(input())
for test in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	s = [0 for i in range(n)]
	res = 0
	for i in range(n):
		res = res + max(0, a[i] - s[i] - 1)
		for j in range(i + 2, min(n, i + a[i] + 1)):
			s[j] += 1
		if i < n - 1 and s[i] >= a[i]:
			s[i + 1] = s[i + 1] + s[i] - a[i] + 1
	print(res)


import sys
import math

class DictList(dict):

	def __setitem__(self, key, value):
		try:
			self[key].append(value)
		except KeyError:
			super(DictList, self).__setitem__(key, value)
		except AttributeError:
			super(DictList, self).__setitem__(key, [self[key], value])

def fn(n, s):
	count = [0] * n
	c = 0
	i = 0
	for i in range(n):
		if s[i] > 1:
			m = min(i + s[i], n - 1)
			for j in range(i + 2, m + 1):
				count[j] = count[j] + 1
	for i in range(n - 1):
		if s[i] - 1 - count[i] < 0:
			count[i + 1] = count[i + 1] + abs(s[i] - 1 - count[i])
	for i in range(n):
		if s[i] > 0:
			c = c + max(0, s[i] - 1 - count[i])
	return c
input = sys.stdin.read()
data = list(map(int, input.split()))
t = data[0]
l = 0
for i in range(t):
	n = data[l + 1]
	s = data[l + 2:l + 2 + n]
	l = l + 1 + n
	print(fn(n, s))


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import math
alphabets = list('abcdefghijklmnopqrstuvwxyz')

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

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

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def si():
	return input()

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

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

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

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')

def power_set(L):
	cardinality = len(L)
	n = 2 ** cardinality
	powerset = []
	for i in range(n):
		a = bin(i)[2:]
		subset = []
		for j in range(len(a)):
			if a[-j - 1] == '1':
				subset.append(L[j])
		powerset.append(subset)
	powerset_orderred = []
	for k in range(cardinality + 1):
		for w in powerset:
			if len(w) == k:
				powerset_orderred.append(w)
	return powerset_orderred

def fastPlrintNextLines(a):
	print('\n'.join(map(str, a)))

def sortByFirstAndSecond(A):
	A = sorted(A, key=lambda x: x[0])
	A = sorted(A, key=lambda x: x[1])
	return list(A)
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def solve():
	n = ii()
	s = li()
	res = 0
	cnt = [0] * n
	for i in range(n):
		if 1:
			x = s[i]
			s[i] = 1
			y = x - 1
			if y > cnt[i]:
				res += y - cnt[i]
			elif y != cnt[i]:
				if i != n - 1:
					cnt[i + 1] += cnt[i] - y
			if x != 1:
				for j in range(i + 2, i + x + 1):
					if j >= n:
						break
					cnt[j] += 1
	print(res)
t = 1
t = int(input())
for _ in range(t):
	solve()


import sys
input = sys.stdin.readline

def main():
	n = int(input())
	slst = list(map(int, input().split()))
	ans = 0
	minus = [0] * (n + 1)
	for (i, s) in enumerate(slst):
		tmp = s - 1
		for j in range(2, s + 1):
			pos = i + j
			try:
				minus[pos] += 1
			except:
				break
		if tmp - minus[i] > 0:
			ans += tmp - minus[i]
		else:
			minus[i + 1] += minus[i] - tmp
	print(ans)
for _ in range(int(input())):
	main()


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	S = list(map(int, input().split()))
	todo = [0] * n
	out = 0
	for i in range(n):
		need = S[i] - 1
		smol = todo[i]
		act = max(smol, need)
		out += act - smol
		for j in range(2, S[i] + 1):
			if i + j >= n:
				break
			todo[i + j] += 1
		if i != n - 1:
			todo[i + 1] += act - need
	print(out)


t = int(input())
for _ in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	minus = [0] * n
	ans = 0
	for i in range(n):
		ans += nums[i] - minus[i] - 1
		cur = 0
		for j in range(i + 2, n):
			if j <= i + nums[i]:
				cur += 1
			if not cur:
				break
			if nums[j] - minus[j] - cur >= 1:
				minus[j] += cur
				cur = 0
			else:
				p = nums[j] - minus[j] - 1
				minus[j] += p
				cur -= p
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	cur = [0] * (n + 10)
	ans = 0
	for i in range(n):
		diff = cur[i] - arr[i]
		if diff >= 0:
			cur[i + 1] += diff + 1
		else:
			ans += abs(diff)
			cur[i + 1] += 1
		for j in range(i + 2, min(n, i + arr[i] + 1)):
			cur[j] += 1
	print(ans - 1)


import math
from collections import deque
from sys import stdin, stdout, setrecursionlimit
from string import ascii_letters
from decimal import *
letters = ascii_letters[:26]
from collections import defaultdict
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	res = 0
	was = [0] * (n + 1)
	for i in range(n):
		if arr[i] > n - i - 1:
			if n - i - 1 > 0:
				v = arr[i] - (n - i - 1)
				res += max(0, v - was[i])
				was[i] -= min(v, was[i])
				arr[i] = n - i - 1
			else:
				v = arr[i] - 1
				res += max(0, v - was[i])
				was[i] -= min(v, was[i])
				arr[i] = 1
		for g in range(2, arr[i] + 1):
			was[i + g] += 1
			if was[i] > 0:
				was[i] -= 1
			else:
				res += 1
		was[i + 1] += was[i]
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [0] + [int(i) for i in input().split()]
	dp = [0] * (n + 5)
	res = 0
	cnt = 0
	s = 0
	for i in range(1, n + 1):
		s += dp[i]
		cnt += s
		if cnt >= a[i] - 1:
			cnt -= a[i]
			cnt += 1
		else:
			res += a[i]
			res -= cnt
			res -= 1
			cnt = 0
		dp[i + 2] += 1
		mi = min(i + a[i] + 1, n + 1)
		dp[mi] -= 1
	print(res)


import sys
import math
from collections import Counter, defaultdict
LI = lambda : list(map(int, input().split()))
MAP = lambda : map(int, input().split())
IN = lambda : int(input())
S = lambda : input()

def case():
	n = IN()
	a = LI()
	b = [0] * n
	ans = 0
	for i in range(n):
		x = a[i] - 1 - b[i]
		ans += max(0, x)
		if x < 0 and i != n - 1:
			b[i + 1] -= x
		for j in range(i + 2, min(a[i] + i + 1, n)):
			b[j] += 1
	print(ans)
for _ in range(IN()):
	case()


def main():
	t = int(input())
	result = []
	for _ in range(t):
		n = int(input())
		s = list(map(int, input().split()))
		ans = 0
		jumps_cnt = [0] * (n + 1)
		for i in range(n):
			curr_jumps = jumps_cnt[i]
			if curr_jumps < s[i] - 1:
				ans += s[i] - 1 - curr_jumps
				curr_jumps += s[i] - 1 - curr_jumps
			jumps_cnt[i + 1] += curr_jumps - (s[i] - 1)
			for j in range(i + 2, min(n, i + s[i] + 1)):
				jumps_cnt[j] += 1
		result.append(str(ans))
	print('\n'.join(result))
main()


import os, sys, math
from io import BytesIO, IOBase
from collections import defaultdict, deque, OrderedDict
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(input())

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

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

def Sn():
	return input().strip()
BUFSIZE = 8192

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return len(a)

def solve():
	n = I()
	l = list(In())
	dp = [0] * (n + 5)
	ans = 0
	for i in range(n):
		t = dp[i]
		if t < l[i] - 1:
			ans += l[i] - 1 - t
			t += l[i] - 1 - t
		dp[i + 1] += t - l[i] + 1
		for j in range(i + 2, min(n, i + l[i] + 1)):
			dp[j] += 1
	print(ans)
	pass

def main():
	T = I()
	for i in range(T):
		solve()
M = 998244353
P = 1000000007

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def main():
	t = int(input())
	for i in range(t):
		print(solve())

def add_range(pos, _range, array, diff):
	n = len(array)
	(start, end) = _range
	if pos + start < n:
		array[pos + start] += diff
		if pos + end < n:
			array[pos + end] -= diff
	return array

def solve():
	n = int(input())
	strength = list(map(int, input().split()))
	diff = [0 for _ in range(n)]
	ans = 0
	deq = 0
	for i in range(n):
		deq += diff[i]
		s = strength[i]
		ans += max(s - 1 - deq, 0)
		diff = add_range(i, [2, s + 1], diff, 1)
		if s - 1 < deq:
			diff = add_range(i, [1, 2], diff, deq - s + 1)
	return ans
main()


from sys import *
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	l = [int(x) for x in stdin.readline().split()]
	ind = 0
	ans = 0
	sp = [0] * n
	while ind < n and l[ind] == 1:
		ind += 1
	if ind == n:
		print(0)
		continue
	while ind < n:
		if l[ind] == 1:
			if sp[ind] > 0 and ind < n - 1:
				sp[ind + 1] += sp[ind]
			ind += 1
			continue
		if l[ind] - sp[ind] < 1:
			t = sp[ind] - l[ind] + 1
			if ind < n - 1:
				sp[ind + 1] += t
		for i in range(min(n, ind + 2), min(n, ind + l[ind] + 1)):
			sp[i] += 1
		ans += max(0, l[ind] - 1 - sp[ind])
		ind += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	prev = [0] * n
	res = 0
	for i in range(n):
		a[i] -= 1
	for i in range(n - 1):
		if prev[i] > a[i]:
			prev[i + 1] += prev[i] - a[i]
		if a[i] > n - i - 2:
			res += a[i] - (n - i - 2)
			a[i] = n - i - 2
		for j in range(i + 2, i + a[i] + 2):
			prev[j] += 1
	res += max(prev[-1], a[-1])
	print(res)


import sys
input = sys.stdin.readline

def solution(n, a):
	s_s_p = [0 for _ in range(n)]
	s_s_p[-1] = a[-1] - 1
	if n > 1:
		s_s_p[-2] = a[-2] - 1
	for p in range(n - 3, -1, -1):
		val = a[p]
		if val > 1:
			if p + val > n - 1:
				s_s_p[p] += p + val - (n - 1)
			carry = 0
			for r in range(p + 2, n):
				if r <= p + val:
					carry += 1
				if carry >= s_s_p[r]:
					carry -= s_s_p[r]
					s_s_p[p] += s_s_p[r]
					s_s_p[r] = 0
				else:
					s_s_p[r] -= carry
					s_s_p[p] += carry
					carry = 0
			s_s_p[p] += carry
	print(sum(s_s_p))
T = int(input())
for t in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	solution(n, a)


import sys
input = sys.stdin.readline
flush = sys.stdout.flush
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	B = [0] * n
	ans = 0
	for i in range(n):
		if A[i] - B[i] > 1:
			ans += A[i] - B[i] - 1
			B[i] = A[i] - 1
		for j in range(i + 2, min(n, i + A[i] + 1)):
			B[j] += 1
		if i + 1 < n:
			B[i + 1] += B[i] - (A[i] - 1)
	print(ans)


import sys
input = sys.stdin.readline

def slow_solve(n, Ss):
	ans = 0
	for i in range(n):
		if Ss[i] >= n - i:
			ans += Ss[i] - (n - i)
			Ss[i] = n - i
		while Ss[i] > 1:
			ans += 1
			cur = i
			while cur < n:
				pre = cur
				cur += Ss[cur]
				if Ss[pre] > 1:
					Ss[pre] -= 1
	return ans

def solve(n, Ss):
	ans = 0
	jumps = [0] * n
	for i in range(n - 1):
		if Ss[i] >= n - i - 1:
			spare = min(jumps[i], Ss[i] - (n - i - 1))
			ans += Ss[i] - (n - i - 1) - spare
			jumps[i] -= spare
			Ss[i] = n - i - 1
		if Ss[i] > 1:
			ans += max(Ss[i] - 1 - jumps[i], 0)
			for t in range(i + 2, i + Ss[i] + 1):
				jumps[t] += 1
		if Ss[i] - 1 < jumps[i]:
			jumps[i + 1] += jumps[i] - (Ss[i] - 1)
	ans += max(Ss[-1] - 1 - jumps[-1], 0)
	return ans
t = int(input())
answers = []
for _ in range(t):
	n = int(input())
	Ss = list(map(int, input().split()))
	answers.append(solve(n, Ss))
print('\n'.join(map(str, answers)))


for _ in range(int(input())):
	n = int(input())
	s = [int(i) for i in input().split()]
	passes = 0
	jumps = [0] * (n + 1)
	for ind in range(n):
		jump = jumps[ind]
		if s[ind] - 1 > jump:
			passes += s[ind] - 1 - jump
			jump += s[ind] - 1 - jump
		jumps[ind + 1] += jump - s[ind] + 1
		for inner_ind in range(ind + 2, min(n, ind + 1 + s[ind])):
			jumps[inner_ind] += 1
	print(passes)


TC = int(input())
for tc in range(TC):
	n = int(input())
	arr = list(map(int, input().split()))
	curr = [0] * (n + 5)
	ans = 0
	for x in range(n):
		temp = curr[x]
		if temp < arr[x] - 1:
			ans += arr[x] - 1 - temp
			temp += arr[x] - 1 - temp
		curr[x + 1] += temp - arr[x] + 1
		for y in range(x + 2, min(n, x + arr[x] + 1)):
			curr[y] += 1
	print(ans)


def solve(N, nums):
	ans = 0
	for i in range(N):
		temp = 0
		for j in range(i):
			temp += max(0, nums[j] - (i - j))
		ans = max(ans, temp + nums[i] - 1)
	return ans
T = int(input())
for _ in range(T):
	N = int(input())
	nums = list(map(int, input().split()))
	ans = solve(N, nums)
	print(ans)


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest
from copy import deepcopy
mod = 10 ** 9 + 7
INF = float('inf')

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

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

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def inps():
	return sys.stdin.readline()

def inpsl(x):
	tmp = sys.stdin.readline()
	return list(tmp[:x])

def err(x):
	print(x)
	exit()
for _ in range(inp()):
	n = inp()
	a = inpl()
	res = 0
	cnt = [0] * n
	for (i, x) in enumerate(a):
		now = x - cnt[i]
		if now > 1:
			res += now - 1
		if now <= 0 and i < n - 1:
			cnt[i + 1] += 1 - now
		for j in range(x - 1):
			if i + 2 + j >= n:
				break
			cnt[i + 2 + j] += 1
	print(res)


import sys
pin = sys.stdin.readline

def aupdate(n, v):
	while n < len(tree):
		tree[n] += v
		n += n & -n

def update(l, d, v):
	aupdate(l, v)
	aupdate(l + d, -v)

def query(n):
	ans = 0
	while n:
		ans += tree[n]
		n -= n & -n
	return ans
for T in range(int(pin())):
	N = int(pin())
	A = [*map(int, pin().split())]
	tree = [0 for _ in range(N + 2)]
	S = 0
	for n in range(1, N + 1):
		C = A[n - 1] - query(n)
		S += max(C - 1, 0)
		if C < 1:
			update(n + 1, 1, 1 - C)
		if A[n - 1] == 1:
			continue
		else:
			update(n + 2, A[n - 1] - 1, 1)
	print(S)


import io, sys, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def printArr(arr):
	sys.stdout.write(' '.join(map(str, arr)) + '\n')

def solve(arr, n):
	answer = 0
	visited = [0 for i in range(n + 1)]
	for i in range(n):
		vis = visited[i]
		if arr[i] - 1 > vis:
			answer += arr[i] - 1 - vis
		else:
			visited[i + 1] += vis - arr[i] + 1
		for j in range(i + 2, min(n, arr[i] + i + 1)):
			visited[j] += 1
	return answer
t = int(input().decode())
while t > 0:
	n = int(input().decode())
	arr = [int(i) for i in input().decode().strip().split()]
	answer = solve(arr, n)
	sys.stdout.write(str(answer) + '\n')
	t -= 1


import os
from io import BytesIO, IOBase
import sys
from collections import defaultdict, deque, Counter
from bisect import *
from math import sqrt, pi, ceil, log, inf, gcd, floor
from itertools import permutations
from copy import deepcopy
from heapq import *

def lcm(a, b):
	return a * b // gcd(a, b)

def fact(n, mo):
	f = [1]
	for i in range(1, n + 1):
		f.append(f[-1] * i % mo)
	invf = [0] * (n + 1)
	invf = pow(f[-1], mo - 2, mo)
	for i in range(n - 1, -1, -1):
		invf[i] = (i + 1) * invf[i + 1] % mo
	return (f, invf)

def mod(a, m):
	if a > m:
		return a % m
	return a

def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		if a.count(1) == n:
			print(0)
		else:
			(pre, suff) = ([0] * (n + 1), [0] * (n + 1))
			extra = z = 0
			for i in range(n):
				extra += pre[i] + suff[i]
				y = extra
				if y > a[i]:
					(pre[i + 1], y) = (pre[i + 1] + y - a[i] + 1, a[i] - 1)
				suff[min(n, i + a[i] + 1)] -= 1
				suff[min(n, i + a[i] - y + 1)] += 1
				a[i] = max(1, a[i] - extra)
				z += a[i] - 1
				suff[min(n, i + a[i] + 1)] -= 1
				suff[min(n, i + 2)] += 1
				(a[i], extra) = (1, extra - pre[i])
			print(z)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def solution(n):
	pref = [0 for _ in range(n + 1)]
	s = [int(i) for i in input().split()]
	for i in range(n):
		if s[i] > 1:
			pref[min(i + 2, n)] += 1
			pref[min(s[i] + 1 + i, n)] -= 1
	for i in range(n):
		pref[i + 1] += pref[i]
	for i in range(n):
		if pref[i] - s[i] + 1 > 0:
			pref[i + 1] += pref[i] - s[i] + 1
	ans = 0
	for i in range(n):
		ans += max(s[i] - pref[i] - 1, 0)
	print(ans)
for t in range(int(input())):
	n = int(input())
	solution(n)


import sys
input = sys.stdin.readline

def getvalue(n, seg_el):
	i = n + seg_el
	ANS = 0
	ANS = SEG[i]
	i >>= 1
	while i != 0:
		ANS += SEG[i]
		i >>= 1
	return ANS

def updates(l, r, x):
	L = l + seg_el
	R = r + seg_el
	while L < R:
		if L & 1:
			SEG[L] += x
			L += 1
		if R & 1:
			R -= 1
			SEG[R] += x
		L >>= 1
		R >>= 1
t = int(input())
for tests in range(t):
	n = int(input())
	S = list(map(int, input().split()))
	seg_el = 1 << (n + 1).bit_length()
	SEG = [0] * (2 * seg_el)
	for i in range(n):
		SEG[i + seg_el] = S[i]
	ANS = 0
	for i in range(n):
		x = getvalue(i, seg_el)
		if x >= 2:
			ANS += x - 1
		if i + 2 < n:
			updates(i + 2, min(i + 2 + S[i] - 1, n), -1)
		if x <= 0:
			y = 1 - x
			if i + 1 < n:
				updates(i + 1, i + 2, -y)
	print(ANS)


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

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

def MI():
	return map(int, sys.stdin.buffer.readline().split())

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

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()
inf = 10 ** 16
md = 10 ** 9 + 7
for _ in range(II()):
	n = II()
	aa = LI()
	bb = [0] * (n + 1)
	ans = 0
	for i in range(n):
		ans += max(0, aa[i] - 1 - bb[i])
		for j in range(i + 2, min(n, i + aa[i] + 1)):
			bb[j] += 1
		rem = bb[i] - aa[i] + 1
		if rem > 0:
			bb[i + 1] += rem
	print(ans)


import sys
input = sys.stdin.readline
for nt in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	c = [0] * n
	for i in range(n):
		if a[i] > c[i] + 1:
			ans += a[i] - c[i] - 1
			c[i] += a[i] - c[i] - 1
		if i != n - 1:
			c[i + 1] += c[i] - a[i] + 1
		for j in range(min(i + a[i], n - 1), i + 1, -1):
			c[j] += 1
	print(ans)


import sys
input = sys.stdin.readline
t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	l = [0] * n
	ans = 0
	for i in range(n):
		x = a[i] - 1 - l[i]
		ans += max(x, 0)
		for j in range(min(a[i], n - i - 1) - 1):
			l[i + 2 + j] += 1
		if x < 0:
			x = abs(x)
			if i < n - 1:
				l[i + 1] += x
	print(ans)
	t -= 1


import sys
from math import log2
from collections import defaultdict

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

def MI():
	return map(int, sys.stdin.buffer.readline().split())

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

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()
for _ in range(II()):
	n = II()
	ans = 0
	a = LI()
	d = [0] * (n + 2)
	for i in range(n):
		tmp = d[i]
		if tmp < a[i] - 1:
			ans += a[i] - tmp - 1
			tmp += a[i] - 1 - tmp
		d[i + 1] += tmp - a[i] + 1
		if i + 2 < n:
			for j in range(i + 2, min(n, i + a[i] + 1)):
				d[j] += 1
	print(ans)


p = lambda : list(map(int, input().split()))
exec('N=p()[0];s=p();print(max(s[i]+sum([max(0,s[j]-i+j)for j in range(i)])-1for i in range(N)));' * p()[0])


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

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

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

def N():
	return int(input())

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

def print_list(l):
	print(' '.join(map(str, l)))
for _ in range(N()):
	n = N()
	a = RLL()
	c = [1] * (n + 1)
	ans = 0
	for i in range(n):
		if a[i] > c[i]:
			ans += a[i] - c[i]
		else:
			c[i + 1] += c[i] - a[i]
		for j in range(i + 2, min(n, i + a[i] + 1)):
			c[j] += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	dp = []
	dp.append([max(0, a[0] - 1)])
	dp[0].append(0)
	for i in range(1, n):
		temp = 0
		for j in range(0, i - 1):
			if a[j] + j >= i:
				temp += 1
		temp += dp[i - 1][1]
		if temp >= a[i] - 1:
			dp.append([dp[i - 1][0]])
			dp[i].append(temp + 1 - a[i])
		else:
			dp.append([dp[i - 1][0] + a[i] - 1 - temp])
			dp[i].append(0)
	print(dp[n - 1][0])


import sys, math
import io, os
from collections import defaultdict as dd, deque, Counter

def data():
	return sys.stdin.buffer.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
mod = int(1000000000.0) + 7
for t in range(int(data())):
	n = int(data())
	S = mdata()
	ans = 0
	l = [0] * (n + 1)
	for i in range(n):
		if S[i] - 1 > l[i]:
			ans += S[i] - l[i] - 1
		else:
			l[i + 1] += l[i] - S[i] + 1
		for j in range(i + 2, min(i + S[i] + 1, n)):
			l[j] += 1
	out(ans)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	s = list(map(int, input().split()))
	z = list(range(n))
	r = 0
	for i in range(n):
		v = s[i]
		if v + i > n - 1:
			v = max(n - 1 - i, 1)
			if s[i] != v:
				r += s[i] - v
				s[i] = v
		while s[i] > 1:
			r += 1
			p = i
			while p < n:
				p = z[p]
				v = s[p]
				if v == 1:
					f = n - 1
					j = p
					while j < f:
						if s[j] != 1:
							f = j
							break
						elif z[j] == j:
							z[j] = j + 1
							j += 1
						else:
							j = z[j]
					k = p
					while k < f:
						v = z[k]
						z[k] = f
						k = v
					p = f
					v = s[p]
				if v > 1:
					s[p] = v - 1
				p += v
	return r
t = int(input())
r = [0] * t
for z in range(t):
	r[z] = str(solve())
print('\n'.join(r))


import sys, functools, collections, bisect, math, heapq
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	count = 0
	pre_count = [0] * n
	for i in range(n):
		temp = arr[i] - pre_count[i] - 1
		if temp > 0:
			count += temp
		elif i + 1 < n:
			pre_count[i + 1] -= temp
		for j in range(i + 2, min(n, i + arr[i] + 1)):
			pre_count[j] += 1
	print(count)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	ans = 0
	s = list(map(int, input().split()))
	l = [0] * (n + 1)
	for i in range(n):
		if s[i] <= l[i]:
			l[i + 1] += l[i] - s[i] + 1
		ans += max(0, s[i] - l[i] - 1)
		for j in range(min(s[i], n - i - 1), 1, -1):
			l[i + j] += 1
	print(ans)


import sys
input = sys.stdin.readline

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

def II():
	return int(input().strip())

def LI():
	return [*map(int, input().strip().split())]
import string, math, time, functools, random, fractions
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter, OrderedDict
from itertools import permutations, combinations, groupby
for _ in range(II()):
	n = II()
	s = LI()
	cnt = [1] * n
	ans = 0
	for i in range(n):
		if s[i] > cnt[i]:
			ans += s[i] - cnt[i]
		if i + 2 < n:
			for j in range(i + 2, min(n, i + 2 + s[i] - 1)):
				cnt[j] += 1
		if i + 1 < n:
			if cnt[i] > s[i]:
				cnt[i + 1] += cnt[i] - s[i]
	print(ans)


import sys
import math
import heapq
import bisect
from collections import Counter
from collections import defaultdict
from io import BytesIO, IOBase
import string

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None
		self.BUFSIZE = 8192

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_int():
	return int(input())

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

def get_int_grid(n):
	return [get_ints() for _ in range(n)]

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

def get_strs():
	return input().strip().split(' ')

def yes_no(b):
	if b:
		return 'YES'
	else:
		return 'NO'

def binary_search(good, left, right, delta=1, right_true=False):
	limits = [left, right]
	while limits[1] - limits[0] > delta:
		if delta == 1:
			mid = sum(limits) // 2
		else:
			mid = sum(limits) / 2
		if good(mid):
			limits[int(right_true)] = mid
		else:
			limits[int(~right_true)] = mid
	if good(limits[int(right_true)]):
		return limits[int(right_true)]
	else:
		return False

def prefix_sums(a, drop_zero=False):
	p = [0]
	for x in a:
		p.append(p[-1] + x)
	if drop_zero:
		return p[1:]
	else:
		return p

def prefix_mins(a, drop_zero=False):
	p = [float('inf')]
	for x in a:
		p.append(min(p[-1], x))
	if drop_zero:
		return p[1:]
	else:
		return p

def solve_a():
	(n, q) = get_ints()
	a = get_ints()
	s = sum(a)
	ans = []
	for query in range(q):
		(t, k) = get_ints()
		if t == 1:
			if a[k - 1] == 1:
				a[k - 1] = 0
				s -= 1
			else:
				a[k - 1] = 1
				s += 1
		else:
			ans.append(int(s >= k))
	return ans

def solve_b():
	(n, u, v) = get_ints()
	a = get_ints()
	if min(a) == max(a):
		return min(v * 2, u + v)
	else:
		for i in range(1, n):
			if abs(a[i] - a[i - 1]) >= 2:
				return 0
		return min(u, v)

def solve_c():
	n = get_int()
	arr = get_ints()
	curr = [0] * (n + 1)
	ans = 0
	for x in range(n):
		temp = curr[x]
		if temp < arr[x] - 1:
			ans += arr[x] - 1 - temp
			temp += arr[x] - 1 - temp
		curr[x + 1] += temp - arr[x] + 1
		for y in range(x + 2, min(n, x + arr[x] + 1)):
			curr[y] += 1
	return ans
t = get_int()
for _ in range(t):
	print(solve_c())


res = []
for _ in range(int(input())):
	n = int(input())
	S = list(map(int, input().split()))
	result = 0
	for i in range(n):
		rejumps = 0
		for j in range(i):
			rejumps += max(0, S[j] - (i - j))
		result = max(result, S[i] + rejumps - 1)
	res.append(result)
print(*res, sep='\n')


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	res = 0
	jump = [0] * (n + 1)
	for (i, s) in enumerate(map(int, input().strip().split())):
		if s != 1:
			m = min(n + 1, i + s + 1)
			res += s - m + i + 1
			for x in range(i + 2, m):
				jump[x] += 1
			jump[i] = max(0, jump[i] + 1 - s)
		jump[i + 1] += jump[i]
	print(res + jump[-1])


from collections import defaultdict as dd
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = []
	dp = [0] * n
	extra = [0] * n + [0]
	for i in range(n):
		res = max(0, a[i] - 1 - extra[i])
		if extra[i] > a[i] - 1:
			extra[i + 1] += extra[i] - (a[i] - 1)
		dp[i] = dp[i - 1] + res
		for j in range(i + 2, min(n, i + a[i] + 1)):
			extra[j] += 1
	print(dp[-1])


TC = int(input().strip())
for tc in range(TC):
	n = int(input().strip())
	arr = [int(i) for i in input().strip().split()]
	curr = [0] * (n + 1)
	ans = 0
	for x in range(n):
		temp = curr[x]
		if temp < arr[x] - 1:
			ans += arr[x] - 1 - temp
			y = arr[x] - 1 - temp
			temp += y
		curr[x + 1] += temp - arr[x] + 1
		for y in range(x + 2, min(n, x + arr[x] + 1)):
			curr[y] += 1
	print(ans)


import sys
import io, os
input = sys.stdin.buffer.readline
t = int(input())
for _ in range(t):
	n = int(input())
	S = list(map(int, input().split()))
	C = [0] * n
	ans = 0
	for i in range(n):
		temp = C[i]
		if temp < S[i] - 1:
			ans += S[i] - 1 - temp
			temp += S[i] - 1 - temp
		if i + 1 <= n - 1:
			C[i + 1] += temp - (S[i] - 1)
		if i + 2 <= n - 1:
			for j in range(i + 2, min(n, i + S[i] + 1)):
				C[j] += 1
	print(ans)


import sys, io, os
BUFSIZE = 8192

class FastIO(io.IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = io.BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(io.IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from itertools import accumulate
T = int(input())
for _ in range(T):
	N = int(input())
	S = list(map(int, input().split()))
	Imos = [0] * (N + 2)
	c = 0
	ans = 0
	for idx_S in range(N):
		s = S[idx_S]
		c += Imos[idx_S]
		lack = s - 1 - c
		if 0 < lack:
			ans += lack
		if s >= 2:
			Imos[idx_S + 2] += 1
			if idx_S + s + 1 < N:
				Imos[idx_S + s + 1] -= 1
		if lack < 0:
			Imos[idx_S + 1] += -lack
			Imos[idx_S + 2] -= -lack
	print(ans)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	cur = [0] * (n + 4)
	ans = 0
	for i in range(n):
		t = cur[i]
		if t < a[i] - 1:
			ans += a[i] - 1 - t
			t += a[i] - 1 - t
		cur[i + 1] += t - a[i] + 1
		for j in range(i + 2, min(n, i + a[i] + 1)):
			cur[j] += 1
	print(ans)


import sys
from math import ceil
from _collections import deque
from _collections import OrderedDict
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	n = int(input())
	ar = [0] * n
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		if a[i] != 1:
			t = a[i]
			a[i] = max(1, a[i] - ar[i])
			if ar:
				if t > ar[i]:
					for j in range(i + a[i] + 1, min(n, t + i + 1)):
						ar[j] += 1
				else:
					for j in range(i + 1, min(n, t + i + 1)):
						ar[j] += 1
					if i != n - 1:
						ar[i + 1] += ar[i] - t
			if a[i] != 1:
				for j in range(i + 2, min(i + 1 + a[i], n)):
					ar[j] += 1
				ans += a[i] - 1
		elif i != n - 1:
			ar[i + 1] += ar[i]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	extra = [0] * n
	cost = 0
	for i in range(n):
		if arr[i] == 1:
			if extra[i] > 0:
				if i != n - 1:
					extra[i + 1] += extra[i]
		elif extra[i] + 1 < arr[i]:
			cost += max(0, arr[i] - extra[i] - 1)
			for j in range(min(n - 1, i + arr[i]), min(n - 1, i + 1), -1):
				extra[j] += 1
		else:
			for j in range(min(n - 1, i + arr[i]), min(n - 1, i + 1), -1):
				extra[j] += 1
			if i != n - 1:
				extra[i + 1] += extra[i] + 1 - arr[i]
	print(cost)


ans = []
for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	res = 0
	for i in range(n):
		temp = 0
		for j in range(i):
			temp += max(0, s[j] - (i - j))
		res = max(res, temp + s[i] - 1)
	ans.append(res)
print(*ans, sep='\n')


import sys
from math import factorial, gcd
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest, nsmallest
from itertools import groupby
from copy import deepcopy
MOD = 10 ** 9 + 7
INF = float('inf')
rl = lambda : list(map(int, sys.stdin.readline().split()))
rs = lambda : sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	A = rl()
	bounced = [0] * (n + 1)
	ans = 0
	for i in range(n):
		if A[i] == 1:
			j = i + 1
			while j < n and A[j] == 1:
				j += 1
			if j == n:
				break
			else:
				bounced[j] += bounced[i]
		elif A[i] - bounced[i] <= 1:
			for j in range(i + 2, min(i + A[i] + 1, n)):
				bounced[j] += 1
			j = i + 1
			while j < n and A[j] == 1:
				j += 1
			if j == n:
				break
			else:
				bounced[j] += bounced[i] - A[i] + 1
		else:
			diff = A[i] - bounced[i] - 1
			ans += diff
			for j in range(i + 2, min(i + A[i] + 1, n)):
				bounced[j] += 1
	print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	pass

def binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

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

def lts(l):
	s = ''.join(map(str, l))
	return s

def stl(s):
	l = list(s)
	return l

def sq(a, target, arr=[]):
	s = sum(arr)
	if s == target:
		return arr
	if s >= target:
		return
	for i in range(len(a)):
		n = a[i]
		remaining = a[i + 1:]
		ans = sq(remaining, target, arr + [n])
		if ans:
			return ans

def SieveOfEratosthenes(n):
	cnt = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			cnt += 1
	return cnt

def nCr(n, r):
	f = math.factorial
	return f(n) // f(r) // f(n - r)
mod = int(1000000000.0) + 7

def ssinp():
	return input()

def iinp():
	return int(input())

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

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

def p(xyz):
	print(xyz)

def p2(a, b):
	print(a, b)
import math
for __ in range(iinp()):
	n = iinp()
	tramp = llinp()
	cnt = [0] * (n + 2)
	ans = 0
	for i in range(n):
		if tramp[i] - cnt[i] > 1:
			ans += tramp[i] - (cnt[i] + 1)
		for j in range(i + 2, min(n, i + tramp[i] + 1), 1):
			cnt[j] += 1
		if cnt[i] >= tramp[i] - 1:
			cnt[i + 1] += cnt[i] - (tramp[i] - 1)
	p(ans)


def array(f):
	return list(map(f, input().split()))

def slv():
	n = int(input())
	a = array(int)
	rabbit = [0] * (n + 1)
	ans = 0
	for (i, v) in enumerate(a):
		if v - rabbit[i] > 1:
			new_rabbit = v - rabbit[i] - 1
			rabbit[i] += new_rabbit
			ans += new_rabbit
		for j in range(max(i + v - n, 0), rabbit[i]):
			if i + v - j <= i:
				rabbit[i + 1] += rabbit[i] - j
				break
			rabbit[min(n, i + v - j)] += 1
	print(ans)
	return

def main():
	T = int(input())
	for _ in range(T):
		slv()
main()


def solve():
	t = int(input())
	listOfArr = []
	for x in range(t):
		n = int(input())
		listOfArr.append(list(map(int, input().split())))
	for x in range(t):
		currentArr = listOfArr[x]
		ans = 0
		for y in range(len(currentArr) - 1, -1, -1):
			for z in range(y + 2, min(len(currentArr) - 1, y + currentArr[y]) + 1):
				currentArr[z] -= 1
		for i in range(len(currentArr) - 1):
			if currentArr[i] <= 0:
				currentArr[i + 1] -= abs(currentArr[i]) + 1
			ans += max(0, currentArr[i] - 1)
		ans += max(0, currentArr[-1] - 1)
		print(ans)
solve()


from sys import stdin, stdout, setrecursionlimit
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log, log2
from random import seed, randint
from datetime import datetime
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
from collections import defaultdict as dd
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def smp():
	return map(str, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b

def def_value():
	return 0

def def_inf():
	return inf
for _ in range(iinp()):
	n = iinp()
	a = lmp()
	c = l1d(n + 1)
	ans = 0
	for i in range(n):
		t = c[i]
		if t < a[i] - 1:
			ans += a[i] - t - 1
			t = a[i] - 1
		c[i + 1] += t - a[i] + 1
		for j in range(i + 2, min(n, i + a[i] + 1)):
			c[j] += 1
	print(ans)


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

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

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 998244353
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

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

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
for _ in range(Int()):
	n = Int()
	a = array()
	ans = 0
	i = 0
	jumps = [0] * n
	for i in range(n):
		for j in range(i - 1):
			r = j + a[j]
			l = max(j + 2, r - jumps[j] + 1)
			if i >= l and i <= r:
				jumps[i] += 1
		if i:
			jumps[i] += max(0, jumps[i - 1] - a[i - 1] + 1)
		need = max(0, a[i] - jumps[i] - 1)
		ans += need
		jumps[i] += need
	print(ans)


import sys, collections, math, itertools, random, bisect
INF = sys.maxsize

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

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

def input():
	return sys.stdin.readline().strip()
mod = 1000000007
for _ in range(int(input())):
	n = int(input())
	arr = get_array()
	res = [0] * (n + 1)
	for i in range(n):
		if arr[i] > 1:
			res[min(n, i + 2)] += 1
			res[min(n, i + 1 + arr[i])] -= 1
	for i in range(n):
		res[i + 1] += res[i]
	for i in range(n):
		val = res[i] - (arr[i] - 1)
		if val > 0:
			res[i + 1] += val
	ans = 0
	for i in range(n):
		ans += max(0, arr[i] - 1 - res[i])
	print(ans)


import math

def getint():
	return [int(i) for i in input().split()]

def getstr():
	return [str(i) for i in input().split()]

def solve():
	n = int(input())
	a = getint()
	ans = 0
	debt = 0
	k = 0
	kmap = dict()
	for i in range(n):
		k -= kmap.get(i, 0)
		ans += max(a[i] - (debt + k), 0)
		debt = max(debt + k - a[i], 0)
		k += 1
		kmap[i + a[i] + 1] = kmap.get(i + a[i] + 1, 0) + 1
	print(ans - 1)
for _ in range(int(input())):
	solve()


from sys import stdin, stdout
from math import gcd, sqrt, factorial, pi, inf
from collections import deque, defaultdict
from bisect import bisect, bisect_left
from itertools import permutations as per
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
L = lambda : list(R())
P = lambda x: stdout.write(str(x) + '\n')
nCr = lambda x, y: f[x] * inv(f[y] * f[x - y] % N) % N
inv = lambda x: pow(x, N - 2, N)
lcm = lambda x, y: x * y // gcd(x, y)
hg = lambda x, y: (y + x - 1) // x * x
pw = lambda x: 1 if x == 1 else 1 + pw(x // 2)
chk = lambda x: chk(x // 2) if not x % 2 else True if x == 1 else False
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7
for i in range(I()):
	n = I()
	a = L()
	v = [0] * n
	ans = 0
	p = 0
	for i in range(n):
		p += v[i]
		ans += max(0, a[i] - p - 1)
		if p == 0 and a[i] == 1:
			continue
		if i + a[i] + 1 < n:
			v[i + a[i] + 1] -= 1
		j = min(max(a[i] - p, 0), 1) + i
		if j + 1 < n:
			v[j + 1] += 1
			if a[i] - p <= 0:
				v[j + 1] += abs(a[i] - p)
				if j + 2 < n:
					v[j + 2] -= abs(a[i] - p)
	print(ans)


from sys import stdin
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	s = [int(x) for x in input().split()]
	a = []
	for i in range(n):
		a.append((i + 1, i))
		a.append((s[i] + i, i))
	a.sort()
	j = 0
	o = set()
	ans = 0
	b = []
	for i in range(n):
		while a[j][0] < i:
			if a[j][1] in o:
				o.remove(a[j][1])
			else:
				o.add(a[j][1])
			j += 1
		b.append(s[i] - 1 - len(o))
	for i in range(len(b) - 1):
		if b[i] < 0:
			b[i + 1] -= abs(b[i])
	ans = 0
	for i in b:
		if i > 0:
			ans += i
	print(ans)


import io
import os
from collections import Counter, defaultdict, deque

def solve(N, S):
	if set(S) == {1}:
		return 0
	need = [-1] * N
	freeVisits = [0] * N
	for i in range(N):
		visits = max(S[i] - 1, freeVisits[i])
		need[i] = max(0, visits - freeVisits[i])
		for j in range(i + 2, min(N, i + S[i] + 1)):
			freeVisits[j] += 1
		if i + 1 < N:
			freeVisits[i + 1] += max(0, freeVisits[i] - (S[i] - 1))
		if False:
			print('processed', i)
			print(need)
			print(freeVisits)
	return sum(need)
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = int(input())
for tc in range(1, TC + 1):
	(N,) = [int(x) for x in input().split()]
	S = [int(x) for x in input().split()]
	ans = solve(N, S)
	print(ans)


for rpt in range(int(input())):
	trampoline_count = int(input())
	trampolines = [int(x) for x in input().split()]
	shadow_prefix = [0 for x in range(trampoline_count)]
	res = 0
	current_fix = 0
	for i in range(trampoline_count):
		current_fix += shadow_prefix[i]
		if trampolines[i] - current_fix > 1:
			res += trampolines[i] - current_fix - 1
		if i + 2 < trampoline_count:
			shadow_prefix[i + 2] += 1
		if i + trampolines[i] + 1 < trampoline_count:
			shadow_prefix[i + trampolines[i] + 1] -= 1
		if current_fix >= trampolines[i]:
			if i + 1 < trampoline_count:
				shadow_prefix[i + 1] += current_fix - trampolines[i] + 1
			if i + 2 < trampoline_count:
				shadow_prefix[i + 2] -= current_fix - trampolines[i] + 1
	print(res)


import sys
input = lambda : sys.stdin.readline().rstrip()
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(a) for a in input().split()]
	B = [0] * N
	ans = 0
	for i in range(N):
		a = A[i]
		ans += max(a - 1 - B[i], 0)
		for j in range(2, min(a + 1, N - i)):
			B[i + j] += 1
		if i + 1 < N:
			B[i + 1] += max(B[i] - (a - 1), 0)
	print(ans)


def func(A):
	n = len(A)
	C = [0 for x in range(n)]
	res = 0
	for i in range(n):
		if A[i] - C[i] > 1:
			res += A[i] - 1 - C[i]
			C[i] = A[i] - 1
		try:
			C[i + 1] += C[i] - A[i] + 1
		except:
			pass
		for j in range(i + 2, min(n - 1, i + A[i]) + 1):
			C[j] += 1
	return res
t = int(input())
for i in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	print(func(A))


import sys, io, os
if os.environ['USERNAME'] == 'kissz':
	inp = open('in.txt', 'r').readline

	def debug(*args):
		print(*args, file=sys.stderr)
else:
	inp = sys.stdin.readline

	def debug(*args):
		pass
for _ in range(int(inp())):
	n = int(inp())
	S = [*map(int, inp().split())]
	add = [0] * n
	sub = [0] * n
	cntr = 0
	mod = 0
	for (i, s) in enumerate(S):
		mod += add[i]
		if s - mod > 1:
			cntr += s - mod - 1
		elif i + 1 < n:
			add[i + 1] += mod - s + 1
			sub[i + 1] += mod - s + 1
		if i + 2 < n:
			add[i + 2] += 1
		if i + s < n:
			sub[i + s] += 1
		mod -= sub[i]
	print(cntr)


n = int(input())
while n > 0:
	n -= 1
	counter = 0
	num = int(input())
	arr = list(map(int, input().split()))
	z = [0] * (num + 1)
	for i in range(len(arr)):
		current = z[i]
		if current < arr[i] - 1:
			counter += arr[i] - current - 1
			current += arr[i] - current - 1
		z[i + 1] += current - arr[i] + 1
		for j in range(i + 2, min(num, i + arr[i] + 1)):
			z[j] += 1
	print(counter)


def solve():
	n = int(input())
	s = list(map(int, input().split()))
	on = [0] * n
	ans = 0
	for (i, x) in enumerate(s):
		ans += max(0, x - on[i] - 1)
		on[i] += max(0, x - on[i] - 1)
		for j in range(2, min(n - i, x + 1)):
			on[i + j] += 1
		on[i] -= x - 1
		if i < n - 1 and on[i] > 0:
			on[i + 1] += on[i]
	print(ans)
t = int(input())
for _ in range(t):
	solve()


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
tc = 1
(tc,) = inp()
for _ in range(tc):
	(n,) = inp()
	a = inp()
	ans = 0
	free = [0] * n
	for i in range(n):
		a[i] -= free[i]
		ans += max(0, a[i] - 1)
		for j in range(i + 2, min(n, i + a[i] + free[i] + 1)):
			free[j] += 1 * (a[i] + free[i] > 1)
		if i + 1 < n:
			free[i + 1] += max(0, 1 - a[i])
	print(ans)


test = int(input())
for t in range(test):
	n = int(input())
	s = list(map(int, input().split()))
	r = [0] * n
	res = 0
	for i in range(n):
		b = i + 2
		e = min(i + s[i], n - 1)
		if e >= b:
			for i2 in range(b, e + 1):
				r[i2] += 1
		if i < n - 1 and r[i] > s[i] - 1:
			r[i + 1] += r[i] - s[i] + 1
		s[i] -= r[i]
		if s[i] < 1:
			s[i] = 1
		res += s[i] - 1
	print(res)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	temp = [0 for i in range(n)]
	ans = 0
	for i in range(n):
		curr = temp[i]
		if temp[i] + 1 < arr[i]:
			ans += arr[i] - (curr + 1)
			curr += arr[i] - (curr + 1)
		if i != n - 1:
			temp[i + 1] += curr - arr[i] + 1
		for j in range(i + 2, min(n, arr[i] + i + 1)):
			temp[j] += 1
	print(ans)


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	r = sum(a) - n
	ans = 0
	b = [0] * n
	for i in range(n):
		tmp = b[i]
		for j in range(i + 2, min(i + a[i] + 1, n)):
			b[j] += 1
		tmp -= a[i] - 1
		if b[i] + 1 < a[i]:
			ans += a[i] - (b[i] + 1)
		if tmp > 0 and i < n - 1:
			b[i + 1] += tmp
	print(ans)


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


class BinaryIndexedTree:

	def __init__(self, size):
		self.data = [0] * (size + 1)
		self.msb = 1 << size.bit_length() - 1

	def _add(self, i, w):
		i += 1
		while i < len(self.data):
			self.data[i] += w
			i += i & -i

	def _get_sum(self, i):
		res = 0
		while i > 0:
			res += self.data[i]
			i -= i & -i
		return res

	def __getitem__(self, i):
		if isinstance(i, slice):
			a = self._get_sum(len(self.data) - 1 if i.stop is None else i.stop)
			b = self._get_sum(0 if i.start is None else i.start)
			return a - b
		else:
			return 0
	__setitem__ = _add

	def bisect_left(self, v):
		i = 0
		k = self.msb
		l = len(self.data)
		while k > 0:
			i += k
			if i < l and self.data[i] < v:
				v -= self.data[i]
			else:
				i -= k
			k >>= 1
		return i

	def bisect_right(self, v):
		i = 0
		k = self.msb
		l = len(self.data)
		while k > 0:
			i += k
			if i < l and self.data[i] <= v:
				v -= self.data[i]
			else:
				i -= k
			k >>= 1
		return i
	bisect = bisect_right

def solve(s):
	n = len(s)
	bit = BinaryIndexedTree(n)
	for (i, v) in enumerate(s):
		bit[i] += int(v > 1)
	res = 0
	m = bit[:]
	start = 0
	while m:
		if s[start] == 1:
			start = bit.bisect_right(bit[:start])
		i = start
		if s[i] + i > n:
			t = s[i] + i - n - 1
			res += t
			s[i] -= t
		while i < n:
			if s[i] == 1:
				i = bit.bisect_right(bit[:i])
			else:
				t = s[i]
				s[i] -= 1
				if s[i] == 1:
					bit[i] += -1
					m -= 1
				i += t
		res += 1
	return res
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
m = map(int, read().split())
t = next(m)
tests = []
for _ in range(t):
	n = next(m)
	tests.append([v for (i, v) in zip(range(n), m)])
for s in tests:
	print(solve(s))


def divisors(M):
	d = []
	i = 1
	while M >= i ** 2:
		if M % i == 0:
			d.append(i)
			if i ** 2 != M:
				d.append(M // i)
		i = i + 1
	return d

def popcount(x):
	x = x - (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	x = x + (x >> 16)
	return x & 127

def eratosthenes(n):
	res = [0 for i in range(n + 1)]
	prime = set([])
	for i in range(2, n + 1):
		if not res[i]:
			prime.add(i)
			for j in range(1, n // i + 1):
				res[i * j] = 1
	return prime

def factorization(n):
	res = []
	for p in prime:
		if n % p == 0:
			while n % p == 0:
				n //= p
			res.append(p)
	if n != 1:
		res.append(n)
	return res

def euler_phi(n):
	res = n
	for x in range(2, n + 1):
		if x ** 2 > n:
			break
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res

def ind(b, n):
	res = 0
	while n % b == 0:
		res += 1
		n //= b
	return res

def isPrimeMR(n):
	d = n - 1
	d = d // (d & -d)
	L = [2, 3, 5, 7, 11, 13, 17]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	from math import gcd
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += 1 + i % 2
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def divisors(n):
	res = [1]
	prime = primeFactor(n)
	for p in prime:
		newres = []
		for d in res:
			for j in range(prime[p] + 1):
				newres.append(d * p ** j)
		res = newres
	res.sort()
	return res

def floor_sum(n: int, m: int, a: int, b: int) -> int:
	ans = 0
	if a >= m:
		ans += (n - 1) * n * (a // m) // 2
		a %= m
	if b >= m:
		ans += n * (b // m)
		b %= m
	y_max = (a * n + b) // m
	x_max = y_max * m - b
	if y_max == 0:
		return ans
	ans += (n - (x_max + a - 1) // a) * y_max
	ans += floor_sum(y_max, a, m, (a - x_max % a) % a)
	return ans

def xorfactorial(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	elif num == 2:
		return 3
	elif num == 3:
		return 0
	else:
		x = baseorder(num)
		return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
	if n == 0:
		res = [X[0] * Y[0] % mod]
		return res
	x = [X[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	z = [X[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	res1 = xorconv(n - 1, x, y)
	res2 = xorconv(n - 1, z, w)
	former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
	latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
	former = list(map(lambda x: x % mod, former))
	latter = list(map(lambda x: x % mod, latter))
	return former + latter

def merge_sort(A, B):
	(pos_A, pos_B) = (0, 0)
	(n, m) = (len(A), len(B))
	res = []
	while pos_A < n and pos_B < m:
		(a, b) = (A[pos_A], B[pos_B])
		if a < b:
			res.append(a)
			pos_A += 1
		else:
			res.append(b)
			pos_B += 1
	res += A[pos_A:]
	res += B[pos_B:]
	return res

class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N
		self.group = N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		stack = [x]
		while self._parent[stack[-1]] != stack[-1]:
			stack.append(self._parent[stack[-1]])
		for v in stack:
			self._parent[v] = stack[-1]
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		self.group -= 1
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

class WeightedUnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for i in range(N)]
		self.val = [0 for i in range(N)]
		self.flag = True
		self.edge = [[] for i in range(N)]

	def dfs(self, v, pv):
		stack = [(v, pv)]
		new_parent = self.parent[pv]
		while stack:
			(v, pv) = stack.pop()
			self.parent[v] = new_parent
			for (nv, w) in self.edge[v]:
				if nv != pv:
					self.val[nv] = self.val[v] + w
					stack.append((nv, v))

	def unite(self, x, y, w):
		if not self.flag:
			return
		if self.parent[x] == self.parent[y]:
			self.flag = self.val[x] - self.val[y] == w
			return
		if self.size[self.parent[x]] > self.size[self.parent[y]]:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[x] += self.size[y]
			self.val[y] = self.val[x] - w
			self.dfs(y, x)
		else:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[y] += self.size[x]
			self.val[x] = self.val[y] + w
			self.dfs(x, y)

class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add_edge(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		inf = float('inf')
		que = []
		d = [inf] * self.V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d

def Z_algorithm(s):
	N = len(s)
	Z_alg = [0] * N
	Z_alg[0] = N
	i = 1
	j = 0
	while i < N:
		while i + j < N and s[j] == s[i + j]:
			j += 1
		Z_alg[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < N and k + Z_alg[k] < j:
			Z_alg[i + k] = Z_alg[k]
			k += 1
		i += k
		j -= k
	return Z_alg

class BIT:

	def __init__(self, n):
		self.BIT = [0] * (n + 1)
		self.num = n

	def query(self, idx):
		res_sum = 0
		while idx > 0:
			res_sum += self.BIT[idx]
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		while idx <= self.num:
			self.BIT[idx] += x
			idx += idx & -idx
		return

class dancinglink:

	def __init__(self, n, debug=False):
		self.n = n
		self.debug = debug
		self._left = [i - 1 for i in range(n)]
		self._right = [i + 1 for i in range(n)]
		self.exist = [True for i in range(n)]

	def pop(self, k):
		if self.debug:
			assert self.exist[k]
		L = self._left[k]
		R = self._right[k]
		if L != -1:
			if R != self.n:
				(self._right[L], self._left[R]) = (R, L)
			else:
				self._right[L] = self.n
		elif R != self.n:
			self._left[R] = -1
		self.exist[k] = False

	def left(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._left[res]
			if res == -1:
				break
			k -= 1
		return res

	def right(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._right[res]
			if res == self.n:
				break
			k -= 1
		return res

class SparseTable:

	def __init__(self, A, merge_func, ide_ele):
		N = len(A)
		n = N.bit_length()
		self.table = [[ide_ele for i in range(n)] for i in range(N)]
		self.merge_func = merge_func
		for i in range(N):
			self.table[i][0] = A[i]
		for j in range(1, n):
			for i in range(0, N - 2 ** j + 1):
				f = self.table[i][j - 1]
				s = self.table[i + 2 ** (j - 1)][j - 1]
				self.table[i][j] = self.merge_func(f, s)

	def query(self, s, t):
		b = t - s + 1
		m = b.bit_length() - 1
		return self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])

class BinaryTrie:

	class node:

		def __init__(self, val):
			self.left = None
			self.right = None
			self.max = val

	def __init__(self):
		self.root = self.node(-10 ** 15)

	def append(self, key, val):
		pos = self.root
		for i in range(29, -1, -1):
			pos.max = max(pos.max, val)
			if key >> i & 1:
				if pos.right is None:
					pos.right = self.node(val)
					pos = pos.right
				else:
					pos = pos.right
			elif pos.left is None:
				pos.left = self.node(val)
				pos = pos.left
			else:
				pos = pos.left
		pos.max = max(pos.max, val)

	def search(self, M, xor):
		res = -10 ** 15
		pos = self.root
		for i in range(29, -1, -1):
			if pos is None:
				break
			if M >> i & 1:
				if xor >> i & 1:
					if pos.right:
						res = max(res, pos.right.max)
					pos = pos.left
				else:
					if pos.left:
						res = max(res, pos.left.max)
					pos = pos.right
			elif xor >> i & 1:
				pos = pos.right
			else:
				pos = pos.left
		if pos:
			res = max(res, pos.max)
		return res

def solveequation(edge, ans, n, m):
	x = [0] * m
	used = [False] * n
	for v in range(n):
		if used[v]:
			continue
		y = dfs(v)
		if y != 0:
			return False
	return x

	def dfs(v):
		used[v] = True
		r = ans[v]
		for (to, dire, id) in edge[v]:
			if used[to]:
				continue
			y = dfs(to)
			if dire == -1:
				x[id] = y
			else:
				x[id] = -y
			r += y
		return r

class Matrix:
	mod = 10 ** 9 + 7

	def set_mod(m):
		Matrix.mod = m

	def __init__(self, L):
		self.row = len(L)
		self.column = len(L[0])
		self._matrix = L
		for i in range(self.row):
			for j in range(self.column):
				self._matrix[i][j] %= Matrix.mod

	def __getitem__(self, item):
		if type(item) == int:
			raise IndexError('you must specific row and column')
		elif len(item) != 2:
			raise IndexError('you must specific row and column')
		(i, j) = item
		return self._matrix[i][j]

	def __setitem__(self, item, val):
		if type(item) == int:
			raise IndexError('you must specific row and column')
		elif len(item) != 2:
			raise IndexError('you must specific row and column')
		(i, j) = item
		self._matrix[i][j] = val

	def __add__(self, other):
		if (self.row, self.column) != (other.row, other.column):
			raise SizeError('sizes of matrixes are different')
		res = [[0 for j in range(self.column)] for i in range(self.row)]
		for i in range(self.row):
			for j in range(self.column):
				res[i][j] = self._matrix[i][j] + other._matrix[i][j]
				res[i][j] %= Matrix.mod
		return Matrix(res)

	def __sub__(self, other):
		if (self.row, self.column) != (other.row, other.column):
			raise SizeError('sizes of matrixes are different')
		res = [[0 for j in range(self.column)] for i in range(self.row)]
		for i in range(self.row):
			for j in range(self.column):
				res[i][j] = self._matrix[i][j] - other._matrix[i][j]
				res[i][j] %= Matrix.mod
		return Matrix(res)

	def __mul__(self, other):
		if type(other) != int:
			if self.column != other.row:
				raise SizeError('sizes of matrixes are different')
			res = [[0 for j in range(other.column)] for i in range(self.row)]
			for i in range(self.row):
				for j in range(other.column):
					temp = 0
					for k in range(self.column):
						temp += self._matrix[i][k] * other._matrix[k][j]
					res[i][j] = temp % Matrix.mod
			return Matrix(res)
		else:
			n = other
			res = [[n * self._matrix[i][j] % Matrix.mod for j in range(self.column)] for i in range(self.row)]
			return Matrix(res)

	def __pow__(self, m):
		if self.column != self.row:
			raise MatrixPowError('the size of row must be the same as that of column')
		n = self.row
		res = Matrix([[int(i == j) for i in range(n)] for j in range(n)])
		while m:
			if m % 2 == 1:
				res = res * self
			self = self * self
			m //= 2
		return res

	def __str__(self):
		res = []
		for i in range(self.row):
			for j in range(self.column):
				res.append(str(self._matrix[i][j]))
				res.append(' ')
			res.append('\n')
		res = res[:len(res) - 1]
		return ''.join(res)

class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res

	def bisect_l(self, l, r, x):
		l += self.num
		r += self.num
		Lmin = -1
		Rmin = -1
		while l < r:
			if l & 1:
				if self.tree[l] <= x and Lmin == -1:
					Lmin = l
				l += 1
			if r & 1:
				if self.tree[r - 1] <= x:
					Rmin = r - 1
			l >>= 1
			r >>= 1
		if Lmin != -1:
			pos = Lmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		elif Rmin != -1:
			pos = Rmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		else:
			return -1

class DualSegmentTree:

	def __init__(self, n, segfunc, ide_ele):
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num

	def update(self, l, r, x):
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				self.tree[l] = self.segfunc(self.tree[l], x)
				l += 1
			if r & 1:
				self.tree[r - 1] = self.segfunc(self.tree[r - 1], x)
			l >>= 1
			r >>= 1

	def __getitem__(self, idx):
		idx += self.num
		res = self.ide_ele
		while idx:
			res = self.segfunc(res, self.tree[idx])
			idx >>= 1
		return res

class LazySegmentTree:
	__slots__ = ['merge', 'merge_unit', 'operate', 'merge_operate', 'operate_unit', 'n', 'data', 'lazy']

	def __init__(self, n, init, merge, merge_unit, operate, merge_operate, operate_unit):
		self.merge = merge
		self.merge_unit = merge_unit
		self.operate = operate
		self.merge_operate = merge_operate
		self.operate_unit = operate_unit
		self.n = (n - 1).bit_length()
		self.data = [merge_unit for i in range(1 << self.n + 1)]
		self.lazy = [operate_unit for i in range(1 << self.n + 1)]
		if init:
			for i in range(n):
				self.data[2 ** self.n + i] = init[i]
			for i in range(2 ** self.n - 1, 0, -1):
				self.data[i] = self.merge(self.data[2 * i], self.data[2 * i + 1])

	def propagate(self, v):
		ope = self.lazy[v]
		if ope == self.operate_unit:
			return
		self.lazy[v] = self.operate_unit
		self.data[v << 1] = self.operate(self.data[v << 1], ope)
		self.data[(v << 1) + 1] = self.operate(self.data[(v << 1) + 1], ope)
		self.lazy[v << 1] = self.merge_operate(self.lazy[v << 1], ope)
		self.lazy[(v << 1) + 1] = self.merge_operate(self.lazy[(v << 1) + 1], ope)

	def propagate_above(self, i):
		m = i.bit_length() - 1
		for bit in range(m, 0, -1):
			v = i >> bit
			self.propagate(v)

	def remerge_above(self, i):
		while i:
			c = self.merge(self.data[i], self.data[i ^ 1])
			i >>= 1
			self.data[i] = self.operate(c, self.lazy[i])

	def update(self, l, r, x):
		l += 1 << self.n
		r += 1 << self.n
		l0 = l // (l & -l)
		r0 = r // (r & -r) - 1
		self.propagate_above(l0)
		self.propagate_above(r0)
		while l < r:
			if l & 1:
				self.data[l] = self.operate(self.data[l], x)
				self.lazy[l] = self.merge_operate(self.lazy[l], x)
				l += 1
			if r & 1:
				self.data[r - 1] = self.operate(self.data[r - 1], x)
				self.lazy[r - 1] = self.merge_operate(self.lazy[r - 1], x)
			l >>= 1
			r >>= 1
		self.remerge_above(l0)
		self.remerge_above(r0)

	def query(self, l, r):
		l += 1 << self.n
		r += 1 << self.n
		l0 = l // (l & -l)
		r0 = r // (r & -r) - 1
		self.propagate_above(l0)
		self.propagate_above(r0)
		res = self.merge_unit
		while l < r:
			if l & 1:
				res = self.merge(res, self.data[l])
				l += 1
			if r & 1:
				res = self.merge(res, self.data[r - 1])
			l >>= 1
			r >>= 1
		return res

	def bisect_l(self, l, r, x):
		l += 1 << self.n
		r += 1 << self.n
		l0 = l // (l & -l)
		r0 = r // (r & -r) - 1
		self.propagate_above(l0)
		self.propagate_above(r0)
		Lmin = -1
		Rmin = -1
		while l < r:
			if l & 1:
				if self.data[l][0] <= x and Lmin == -1:
					Lmin = l
				l += 1
			if r & 1:
				if self.data[r - 1][0] <= x:
					Rmin = r - 1
			l >>= 1
			r >>= 1
		res = -1
		if Lmin != -1:
			pos = Lmin
			while pos < self.num:
				self.propagate(pos)
				if self.data[2 * pos][0] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			res = pos - self.num
		if Rmin != -1:
			pos = Rmin
			while pos < self.num:
				self.propagate(pos)
				if self.data[2 * pos][0] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			if res == -1:
				res = pos - self.num
			else:
				res = min(res, pos - self.num)
		return res

def floor_sum(n: int, m: int, a: int, b: int) -> int:
	ans = 0
	if a >= m:
		ans += (n - 1) * n * (a // m) // 2
		a %= m
	if b >= m:
		ans += n * (b // m)
		b %= m
	y_max = (a * n + b) // m
	x_max = y_max * m - b
	if y_max == 0:
		return ans
	ans += (n - (x_max + a - 1) // a) * y_max
	ans += floor_sum(y_max, a, m, (a - x_max % a) % a)
	return ans

def _inv_gcd(a, b):
	a %= b
	if a == 0:
		return (b, 0)
	s = b
	t = a
	m0 = 0
	m1 = 1
	while t:
		u = s // t
		s -= t * u
		m0 -= m1 * u
		(s, t) = (t, s)
		(m0, m1) = (m1, m0)
	if m0 < 0:
		m0 += b // s
	return (s, m0)

def crt(r, m):
	assert len(r) == len(m)
	n = len(r)
	r0 = 0
	m0 = 1
	for i in range(n):
		assert 1 <= m[i]
		r1 = r[i] % m[i]
		m1 = m[i]
		if m0 < m1:
			(r0, r1) = (r1, r0)
			(m0, m1) = (m1, m0)
		if m0 % m1 == 0:
			if r0 % m1 != r1:
				return (0, 0)
			continue
		(g, im) = _inv_gcd(m0, m1)
		u1 = m1 // g
		if (r1 - r0) % g:
			return (0, 0)
		x = (r1 - r0) // g % u1 * im % u1
		r0 += x * m0
		m0 *= u1
		if r0 < 0:
			r0 += m0
	return (r0, m0)
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import log, gcd
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
for _ in range(int(input())):
	n = int(input())
	S = li()
	lazy = [0] * n
	res = 0
	for i in range(n):
		if lazy[i] < S[i]:
			for j in range(i + S[i] - lazy[i] + 1, min(n, i + S[i] + 1)):
				lazy[j] += 1
			S[i] -= lazy[i]
		else:
			for j in range(i + 2, min(n, i + S[i] + 1)):
				lazy[j] += 1
			lazy[i] -= S[i] - 1
			S[i] = 1
			if i != n - 1:
				lazy[i + 1] += lazy[i]
		if S[i] != 1:
			if i + S[i] > n - 1:
				res += i + S[i] - (n - 1)
				S[i] = n - 1 - i
			res += S[i] - 1
			for j in range(i + 2, i + S[i] + 1):
				lazy[j] += 1
	print(res)


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


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	curr = [0] * (n + 5)
	ans = 0
	for i in range(n):
		temp = curr[i]
		if temp < arr[i] - 1:
			ans += arr[i] - 1 - temp
			temp = arr[i] - 1
		curr[i + 1] += temp - arr[i] + 1
		for j in range(i + 2, min(n, i + arr[i] + 1)):
			curr[j] += 1
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	li = [0] * n
	ans = 0
	for i in range(n):
		xx = ar[i] - 1 - li[i]
		tem = max(xx, 0)
		ans += tem
		if xx < 0 and i + 1 < n:
			li[i + 1] += abs(xx)
		for j in range(i + 2, min(i + ar[i] + 1, n)):
			li[j] += 1
	print(ans)


I = input
for _ in range(int(I())):
	n = int(I())
	a = [*map(int, I().split())]
	b = [0] * (n + 1)
	r = 0
	for i in range(n):
		t = b[i]
		if a[i] - 1 > t:
			r += a[i] - 1 - t
			t = a[i] - 1
		b[i + 1] += t - a[i] + 1
		for j in range(i + 2, min(n, i + a[i] + 1)):
			b[j] += 1
	print(r)


import sys
import io
import math
import collections
import decimal
import itertools
import bisect
import heapq

def input():
	return sys.stdin.readline()[:-1]

def solve(N, S):
	n = 0
	T = [0] * N
	for i in range(N):
		if S[i] - 1 > T[i]:
			n += S[i] - 1 - T[i]
			T[i] += S[i] - 1 - T[i]
		if i + S[i] > N:
			a = N - i - S[i]
			T[i] = max(T[i] + a, 0)
			S[i] += a
		while T[i] > 0:
			if S[i] == 1:
				if i + 1 >= N:
					break
				T[i + 1] += T[i]
				T[i] = 0
				break
			else:
				j = i + S[i]
				if j < N:
					T[j] += 1
				S[i] -= 1
				T[i] -= 1
	return n

def main():
	T0 = int(input())
	for _ in range(T0):
		N = int(input())
		S = list(map(int, input().split()))
		ans = solve(N, S)
		print(ans)
main()


from math import *
from collections import *

def solve(n, l):
	cnt = [0 for i in range(n + 5)]
	ans = 0
	for x in range(n):
		temp = cnt[x]
		if temp < l[x] - 1:
			ans += l[x] - 1 - temp
			temp += l[x] - 1 - temp
		cnt[x + 1] += temp - l[x] + 1
		for y in range(x + 2, min(n, x + l[x] + 1)):
			cnt[y] += 1
	return ans
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(solve(n, l))