This is the easy version of this problem. In this version, we do not have queries. Note that we have multiple test cases in this version. You can make hacks only if both versions of the problem are solved.

An array $b$ of length $m$ is good if for all $i$ the $i$-th element is greater than or equal to $i$. In other words, $b$ is good if and only if $b_i \geq i$ for all $i$ ($1 \leq i \leq m$).

You are given an array $a$ consisting of $n$ positive integers. Find the number of pairs of indices $(l, r)$, where $1 \le l \le r \le n$, such that the array $[a_l, a_{l+1}, \ldots, a_r]$ is good.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 2 \cdot 10^5$). Description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$), the length of the array $a$.

The second line of each test case contains $n$ space-separated integers $a_1,a_2,\ldots,a_n$ ($1 \leq a_i \leq n$), representing the array $a$.

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


-----Output-----

For each test case, print the number of suitable pairs of indices.


-----Examples-----

Input
3
3
1 2 3
3
1 1 1
4
2 1 4 3
Output
6
3
7


-----Note-----

In the first test case, all subarrays of $a$ are good, so all pairs are suitable.

In the second test case, the pairs $(1, 1)$, $(2, 2)$, and $(3, 3)$ are suitable. For example, when $(l, r) = (1, 2)$, the array $b=[1,1]$ is not good because $b_2 < 2$.

Difficulty: EASY
Tags: Data structures

Sorting

Amortized analysis
Skill types: Amortized analysis

Sorting

Data structures

Starter code:

Solutions:
n = int(input())
h = []
for i in range(n):
	k = int(input())
	a = list(map(int, input().split()))
	j = 1
	l = 0
	l2 = 0
	ll = 0
	ll2 = 0
	for i in range(k):
		if a[i] >= j:
			l = l + 1
		else:
			j = a[i]
			if l % 2 == 0:
				ll = ll + (l + 1) * (l // 2)
			else:
				ll = ll + ((l + 1) * (l // 2) + l // 2 + 1)
			if l2 % 2 == 0:
				ll = ll - (l2 + 1) * (l2 // 2)
			else:
				ll = ll - ((l2 + 1) * (l2 // 2) + l2 // 2 + 1)
			l2 = a[i] - 1
			l = a[i]
		j = j + 1
	if l % 2 == 0:
		ll = ll + (l + 1) * (l // 2)
	else:
		ll = ll + ((l + 1) * (l // 2) + l // 2 + 1)
	if l2 % 2 == 0:
		ll = ll - (l2 + 1) * (l2 // 2)
	else:
		ll = ll - ((l2 + 1) * (l2 // 2) + l2 // 2 + 1)
	h.append(ll)
for t in h:
	print(t)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	i = 1
	s = 0
	for z in a:
		if z >= i:
			s += i
			i += 1
		else:
			s += z
			i = z + 1
	print(s)


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


def sum(n):
	return (n + 1) * n // 2
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	(ans, now, i) = (0, 0, 0)
	for i in range(n):
		now += 1
		if a[i] < now:
			ans += sum(now - 1) - sum(a[i] - 1)
			now = a[i]
	ans += sum(now)
	print(ans)


import math
import collections
import bisect
import heapq
from collections import deque
from math import sqrt, ceil, floor

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

def inp_int():
	return int(input())

def inp_str():
	return input()

def solve():
	(n,) = inp_arr()
	a = inp_arr()
	ans = 0
	need = 1
	cnt = 0
	diff = 0
	for x in a:
		if x >= need:
			ans += need
			need += 1
		else:
			diff = need - x
			need = need - diff
			ans += need
			need += 1
	print(ans)
tt = inp_int()
for t in range(tt):
	solve()


t = int(input(''))
for i in range(t):
	n = int(input(''))
	l = list(map(int, input('').split()))
	c = 0
	a = 1
	for i in range(n):
		if l[i] >= a:
			c += a
			a += 1
		else:
			c += l[i]
			a = l[i] + 1
	print(c)


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


for _ in range(int(input())):
	n = int(input())
	arr1 = list(map(int, input().split()))
	r = []
	result = 0
	start = 0
	sub = 0
	for i in range(n):
		if i - sub >= arr1[i]:
			sub = -arr1[i] + i + 1
			result += int((start + 1) * start / 2)
			start = arr1[i]
			result -= int(start * (start - 1) / 2)
		else:
			start += 1
	else:
		result += int((start + 1) * start / 2)
	print(result)


def good_subarray(n, a):
	i = 0
	j = 0
	k = 1
	result = 0
	while j < n:
		while i < n and k > a[j]:
			i += 1
			k -= 1
		result += j - i + 1
		j += 1
		k += 1
	return result
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(good_subarray(n, a))


from math import comb

def main():
	n_tests = int(input())
	for _ in range(n_tests):
		n = int(input())
		data = list(map(int, input().split(' ')))
		(result, x) = (0, 0)
		for i in range(1, n + 1):
			x += 1
			x = min(x, i, data[i - 1])
			result += x
		print(result)
main()


from sys import setrecursionlimit, stdin
setrecursionlimit(1 << 20)
readline = stdin.readline
MOD = 998244353

def I():
	return int(readline())

def ST():
	return readline()[:-1]

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

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

def LF(x, func):
	return [func() for _ in [0] * x]

def SPI():
	return map(int, readline().split())

def SPII():
	return map(lambda x: int(x) - 1, readline().split())

def FIE(x):
	return [readline()[:-1] for _ in [0] * x]

def solve():
	N = I()
	A = LI()
	L = 0
	R = 0
	ans = 0
	while True:
		length = R - L
		if R == N:
			break
		if L == R:
			R += 1
			ans += length + 1
		elif A[R] >= length + 1:
			R += 1
			ans += length + 1
		else:
			L += 1
	print(ans)
t = I()
for _ in range(t):
	solve()


t = int(input())
for _ in range(t):
	n = int(input())
	b = [int(x) for x in input().split()]
	tot = 0
	starts = 0
	j = 1
	for i in range(n):
		tot += 1
		if b[i] >= j:
			tot += starts
			starts += 1
			j += 1
		else:
			starts = b[i]
			j = b[i] + 1
			tot += starts - 1
	print(tot)


def cal(n, arr):
	ans = 0
	i = j = 0
	tag = -1
	for i in range(n):
		while j < n and arr[j] + tag - j >= 0:
			j += 1
		if j < n:
			ans += j - i
			tag += 1
		else:
			ans += (j - i) * (j - i + 1) // 2
			break
	return ans
for jj in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	print(cal(n, arr))


def fac(n):
	if n == 1:
		return 1
	p = 1
	for i in range(2, n + 1):
		p *= i
	return p

def cn2(n):
	return n * (n - 1) // 2 + n

def main():
	i = int(input())
	for _ in range(i):
		n = int(input().strip('\r\n'))
		a = [int(x) for x in input().strip('\r\n').split()]
		lens = []
		last_good = 0
		len_good = 0
		res = 0
		j = 0
		start = 0
		while j < n:
			j = start
			i = 0
			while j < n and a[j] > i:
				i += 1
				j += 1
			res += cn2(i)
			if j < n:
				start = j - a[j] + 1
				if a[j] > 1:
					res -= cn2(a[j] - 1)
		print(res)
main()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	i = 0
	j = 0
	z = 0
	while j < n:
		if i != 0 or j != 0:
			i = j - l[j] + 1
			z -= (j - i) * (j - i + 1) / 2
		while j < n and l[j] > j - i:
			j += 1
		z += (j - i) * (j - i + 1) / 2
	print(int(z))


def gcd(y, z):
	while z:
		(y, z) = (z, y % z)
	return abs(y)

def solve():
	n = int(input())
	a = input().split()
	a = [int(x) for x in a]
	i = 0
	j = 0
	res = 0
	while i < n:
		while j < n and a[j] >= j - i + 1:
			j += 1
		res += j - i
		i += 1
	print(res)
t = int(input())
for k in range(t):
	solve()


class T:

	def solve(self):
		n = int(input())
		a = list(map(int, input().split()))
		(i, j, ws, ans) = (0, 0, 1, 0)
		for i in range(n):
			while j < n and ws > a[i]:
				j += 1
				ws -= 1
			ans += i - j + 1
			ws += 1
		return ans
for t in range(int(input())):
	obj = T()
	print(obj.solve())


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


for t in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split(' ')))
	ans = 0
	not_take = 0
	for (i, v) in enumerate(lst):
		if i + 1 > v:
			not_take = max(not_take, i + 1 - v)
		ans += i + 1 - not_take
	print(ans)


from math import gcd

def solve():
	n = int(input())
	a = [int(x) for x in input().split()]
	r = 0
	ans = 0
	for l in range(n):
		while r < l or (r < n and a[r] >= r - l + 1):
			r += 1
		ans += r - l
	print(ans)
t = int(input())
for _ in range(t):
	solve()


import sys
from collections import *
sys.setrecursionlimit(10 ** 5)
itr = (line for line in sys.stdin.read().strip().split('\n'))
INP = lambda : next(itr)

def ni():
	return int(INP())

def nl():
	return [int(_) for _ in INP().split()]

def solve(n, a):
	good = False
	maxlens = [] * n
	possible = 0
	i = 0
	streak = 1
	j = 1
	while i < n:
		while j < n and a[j] >= j - i + 1:
			streak += 1
			j += 1
		possible += streak
		i += 1
		streak -= 1
	print(int(possible))
t = ni()
for case in range(t):
	n = ni()
	a = nl()
	solve(n, a)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	res = [0]
	for i in range(1, n):
		if a[i] > 1:
			capacity = a[i] - 2
			m = min(res[-1], capacity)
			res.append(m + 1)
		else:
			res.append(0)
	print(sum(res) + n)


def foo(n, a):
	ans = [0] * n
	ans[0] = 1
	for i in range(1, n):
		ans[i] = min(ans[i - 1] + 1, i + 1, a[i])
	return sum(ans)
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	print(foo(n, a))


import sys
from math import sqrt, gcd, factorial, ceil, floor, pi, isqrt
from collections import deque, Counter, OrderedDict
from heapq import heapify, heappush, heappop
input = lambda : sys.stdin.readline()
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 10 ** 9 + 7
for _ in range(I()):
	n = I()
	a = L()
	dp = [0] * (n + 1)
	for i in range(1, n + 1):
		dp[i] = min(dp[i - 1] + 1, a[i - 1])
	print(sum(dp))


t = int(input())
for _ in range(t):
	q = int(input())
	a = list(map(int, input().split()))
	r = 0
	y = [0]
	for i in range(q):
		y.append(min(i + 1, a[i], y[i] + 1))
	print(sum(y))


def solve():
	n = int(input())
	a = [int(x) for x in input().split()]
	count = 0
	i = 0
	for j in range(n):
		difference = max(0, j - i + 1 - a[j])
		if i + difference > j:
			i = j + 1
			continue
		i += difference
		count += j - i + 1
	return count
t = int(input())
for _ in range(t):
	print(solve())


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


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	ans = 0
	stk = list()
	for ele in lis:
		while len(stk) >= ele:
			stk.pop()
		stk.append(ele)
		ans += len(stk)
	print(ans)


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


def func(a, n):
	res = 1
	pairs = [0 for _ in range(n)]
	pairs[0] = 1
	for i in range(1, n):
		pairs[i] = min(a[i], i + 1, pairs[i - 1] + 1)
		res += pairs[i]
	return res
T = int(input())
for _ in range(T):
	n = int(input())
	a = [int(a) for a in input().split(' ')]
	print(func(a, n))


n = int(input())
for _ in range(n):
	m = input()
	a = [int(x) for x in input().split(' ')]
	i = 0
	ans = 0
	for j in range(len(a)):
		while True:
			if a[j] >= j - i + 1:
				break
			else:
				i += 1
		ans += j - i + 1
	print(ans)


import os
import math
import collections
import bisect
import functools
import itertools
import heapq

def solve(a, n):
	res = 0
	dp = [0] * (n + 1)
	for i in range(1, n + 1):
		dp[i] = min(dp[i - 1] + 1, a[i - 1])
		res += dp[i]
	return res
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(solve(a, n))


import bisect
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	dp = [0 for i in range(n)]
	dp[0] = 1
	for i in range(1, n):
		dp[i] = min(dp[i - 1] + 1, l[i])
	print(sum(dp))


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

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

def jn(x, l):
	return x.join(map(str, l))

def strl():
	return list(input().strip())

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

def mulf():
	return map(float, input().strip().split())

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

def ceil(x):
	return int(x) if x == int(x) else int(x) + 1

def ceildiv(x, d):
	return x // d if x % d == 0 else x // d + 1
for i in range(inp()):
	n = inp()
	lst = seq()
	cnt = 0
	last = 0
	for i in range(n):
		dx = i - lst[i] + 1
		last = max(last, dx)
		cnt += i - last + 1
	print(cnt)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	i = 0
	j = 0
	k = 1
	ct = 0
	while j < n:
		while i < n and k > l[j]:
			i += 1
			k -= 1
		ct += j - i + 1
		j += 1
		k += 1
	print(ct)


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

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

def S():
	return input()
for _ in range(N()):
	n = N()
	if '5gerg5g' == 282752:
		print('Tanmay')
	a = A()
	c = b = k = 0
	for i in range(n):
		while b < n and a[b] > k:
			b += 1
			k += 1
		c += b - i
		k -= 1
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	ans = 0
	i = 0
	j = 0
	k = 1
	while j < n:
		while i < n and k > lst[j]:
			i += 1
			k -= 1
		ans += j - i + 1
		j += 1
		k += 1
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	i = 0
	j = 0
	k = 1
	ans = 0
	while j < n:
		while i < n and k > arr[j]:
			i += 1
			k -= 1
		ans += j - i + 1
		j += 1
		k += 1
	print(ans)
	t = t - 1


x = int(input())
for i in range(0, x):
	c = input()
	a = list(map(int, input().split()))
	dp = [1 for k in range(0, len(a))]
	s = 1
	for k in range(1, len(a)):
		if a[k] <= a[k - 1]:
			dp[k] = min(dp[k - 1] + 1, a[k])
		else:
			dp[k] = dp[k - 1] + 1
		s = s + dp[k]
	print(s)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(i, j) = (0, 0)
	k = 1
	c = 0
	while j < n:
		while i < n and k > a[j]:
			i += 1
			k -= 1
		c += j - i + 1
		j += 1
		k += 1
	print(c)


test = int(input())
for t in range(test):
	n = int(input())
	A = list(map(int, input().split()))
	count = 0
	i = 0
	j = 0
	k = 1
	while i < n:
		while j < n and k > A[i]:
			j += 1
			k -= 1
		count += i - j + 1
		i += 1
		k += 1
	print(count)


import math
for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	(i, j, k) = (0, 0, 1)
	count = 0
	while i < n:
		while j < n and k > x[i]:
			j += 1
			k -= 1
		count += i - j + 1
		i += 1
		k += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	ans = [1] * n
	i = 0
	j = 0
	k = 1
	while i < n:
		if j < n and l[j] >= k:
			j += 1
			k += 1
		else:
			ans[i] = j - i
			i += 1
			k -= 1
	print(sum(ans))


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	result = 0
	j = 0
	k = 1
	for i in range(n):
		while j < n and k > a[i]:
			j = j + 1
			k = k - 1
		result += i - j + 1
		k = k + 1
	print(result)


for s in [*open(0)][2::2]:
	i = j = r = 0
	for x in s.split():
		while int(x) <= j - i:
			i += 1
		r += j - i + 1
		j += 1
	print(r)


import sys
for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	i = 0
	j = 0
	k = 1
	ans = 0
	while j < n:
		while i < n and k > arr[j]:
			i += 1
			k -= 1
		ans += j - i + 1
		j += 1
		k += 1
	print(ans)


import math
for z in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	(res, i, j) = (0, 0, 0)
	k = 1
	while j < n:
		while i < n and k > a[j]:
			i += 1
			k -= 1
		res += j - i + 1
		j += 1
		k += 1
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	i = 0
	j = 0
	k = 1
	res = 0
	while j < n:
		while i < n and k > a[j]:
			i += 1
			k -= 1
		res += j - i + 1
		j += 1
		k += 1
	print(res)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(i, j) = (0, 0)
	k = 1
	ans = 0
	while j < n:
		while i < n:
			if k > a[j]:
				i += 1
				k -= 1
			else:
				break
		ans += j - i + 1
		j += 1
		k += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	prev = 0
	c = 1
	for i in range(1, n):
		c += min(prev + 1, arr[i] - 1) + 1
		prev = min(prev + 1, arr[i] - 1)
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = input().split()
	arr = [int(i) for i in arr]
	(_sum, eidx, minv) = (0, 0, 0)
	for (i, num) in enumerate(arr):
		while eidx < n:
			if arr[eidx] - eidx - 1 + i < 0:
				break
			eidx += 1
		_sum += eidx - i
	print(_sum)


for _ in range(int(input())):
	(n, li) = (int(input()), [*map(int, input().split())])
	x = z = 0
	(idx, ctr) = (1, 0)
	while x < n:
		while idx > li[x] and z < n:
			z += 1
			idx -= 1
		ctr += x - z + 1
		x += 1
		idx += 1
	print(ctr)


for kfdvb in [*open(0)][2::2]:
	i = j = r = 0
	for c in kfdvb.split():
		j += 1
		i = max(i, j - int(c))
		r += j - i
	print(r)


for _ in range(int(input())):
	n = int(input())
	qu = [int(i) for i in input().split()]
	l = 0
	r = 0
	res = 0
	while l < n:
		while r < n and qu[r] - (r - l + 1) >= 0:
			r += 1
		res += r - l
		l += 1
	print(res)


for stg in [*open(0)][2::2]:
	l = m = n = 0
	for z in stg.split():
		m += 1
		l = max(l, m - int(z))
		n += m - l
	print(n)


import math
testcases = int(input())
while testcases > 0:
	testcases -= 1
	n = int(input())
	a = [int(x) for x in input().split()]
	termination = []
	for i in range(n):
		if a[i] >= i + 1:
			continue
		while len(termination) < i + 1 - a[i]:
			length = len(termination)
			value = i - length
			termination.append(int(value))
	if len(termination) < n:
		while len(termination) < n:
			length = len(termination)
			value = n - length
			termination.append(int(value))
	print(sum(termination))


import math as mm
for _ in range(int(input())):
	size = int(input())
	l = list(map(int, input().split()))
	p = 0
	q = 0
	r = 1
	s = 0
	t = 0
	while q < size:
		t += l[q]
		while r > l[q] and p < size and (q < size):
			p += 1
			r -= 1
		s += q - p + 1
		q += 1
		r += 1
	print(s)


T = int(input())
for i in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	res = 0
	j = 0
	k = 1
	for i in range(N):
		while j < N and k > A[i]:
			j += 1
			k -= 1
		res += i - j + 1
		i += 1
		k += 1
	print(res)


t = eval(input())
for i in range(t):
	n = eval(input())
	a = list(map(int, input().split()))
	dp = [0] * n
	dp[0] = 1
	for i in range(1, n):
		dp[i] = min(i + 1, a[i], dp[i - 1] + 1)
	print(sum(dp))


for p in [*open(0)][2::2]:
	i = 0
	j = 0
	r = 0
	for x in p.split():
		j += 1
		i = max(i, j - int(x))
		r += j - i
	print(r)


for s in [*open(0)][2::2]:
	a = s.split()
	i = j = r = 0
	while j < len(a):
		if int(a[j]) > j - i:
			r += j - i + 1
			j += 1
		else:
			i += 1
	print(r)


import sys
input = sys.stdin.readline
t = []
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	(i, res) = (1, 0)
	before = 0
	for k in a:
		if k >= i:
			i += 1
		else:
			res += i * (i - 1) // 2 - before * (before + 1) // 2
			i = k + 1
			before = k - 1
	res += i * (i - 1) // 2 - before * (before + 1) // 2
	t.append(res)
for x in t:
	print(x)


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	beg = 0
	for j in range(n):
		if a[j] < j - beg + 1:
			s += (j - beg) * (j - beg + 1) // 2
			s -= (a[j] - 1) * a[j] // 2
			beg = j - a[j] + 1
			continue
	s += (n - beg) * (n - beg + 1) // 2
	print(s)


t = int(input())
for test in range(t):
	n = int(input())
	a = [0]
	s = input().split()
	for i in range(n):
		a.append(int(s[i]))
	l = 1
	r = 1
	res = 0
	while True:
		if r < l:
			r = l
		if l == n:
			break
		if r != n:
			if a[r + 1] >= r - l + 2:
				r += 1
				continue
		res += r - l + 1
		l += 1
	print(res + 1)


import sys
input = sys.stdin.readline
for j in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	(ans, val) = (0, 1)
	for i in range(n):
		if arr[i] >= val:
			ans += val
			val += 1
		else:
			ans += arr[i]
			val = arr[i] + 1
	print(ans)


t = []
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	if n == 1:
		t += [1]
		continue
	(i, res) = (1, 0)
	before = 0
	for k in a:
		if k >= i:
			i += 1
		else:
			res += i * (i - 1) // 2 - before * (before + 1) // 2
			i = k + 1
			before = k - 1
	res += i * (i - 1) // 2 - before * (before + 1) // 2
	t.append(res)
for x in t:
	print(x)


output = ''
for caseno in range(int(input())):
	answer = 0
	n = int(input())
	l = list(map(int, input().split()))
	i = 0
	prev = 0
	for i in l:
		curr = min(prev + 1, i)
		prev = curr
		answer += curr
	output += str(answer) + '\n'
print(output)


from sys import stdin
for i in range(int(stdin.readline())):
	n = int(stdin.readline())
	nums = list(map(int, stdin.readline().strip().split()))
	ans = n
	k = 0
	for i in range(n):
		k = max(i - (nums[i] - 1), k)
		ans += min(i - k, nums[i] - 1)
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	i = 0
	j = 0
	while i < n and a[i] >= 1:
		count += j - i
		while j < n and a[j] >= j - i + 1:
			count += 1
			j += 1
		i += 1
	print(count)


from math import comb
for _ in range(int(input())):
	input()
	a = list(map(int, input().split()))
	currentSize = 0
	numbComb = 0
	l = [0 for _ in range(len(a) + 1)]
	for i in range(len(a)):
		for j in range(l[i], len(a)):
			if a[j] <= j - i:
				l[i + 1] = j - 1
				break
		else:
			l[i + 1] = len(a) - 1
	l.pop(0)
	for i in range(len(a)):
		numbComb += l[i] - i + 1
	print(numbComb)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	l = [i - 1 for i in l]
	(k, co, ol) = (0, 0, 0)
	ans = 0
	for i in range(n):
		if l[i] == 0:
			if co > 0:
				ans += (co - ol) * (co - ol + 1) // 2 + ol * (co - ol)
			k = 1
			ol = 0
			co = 1
		elif l[i] >= k:
			co += 1
			k += 1
		else:
			ans += (co - ol) * (co - ol + 1) // 2 + ol * (co - ol)
			ol = l[i]
			k = ol + 1
			co = k
	ans += (co - ol) * (co - ol + 1) // 2 + ol * (co - ol)
	print(ans)


test = int(input())
for _ in range(test):
	n = int(input())
	arr = list(map(int, input().split()))
	stack = []
	cnt = 0
	for i in range(len(arr)):
		while len(stack) != 0:
			if i - stack[0] + 1 > arr[i]:
				del stack[0]
			else:
				cnt += len(stack)
				break
		stack.append(i)
		cnt += 1
	print(cnt)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	ai = list(map(int, input().split()))
	ans = [0 for i in range(n)]
	(l, r) = (0, 0)
	while l < n:
		while r < n:
			if ai[r] < r + 1 - l:
				break
			r += 1
			ans[l] += 1
		l += 1
	for i in range(1, n):
		ans[i] += ans[i - 1] - 1
	print(sum(ans))


def solve(n, a):
	if n == 1:
		return 1
	num_pairs = 0
	(left_index, right_index) = (0, 0)
	while right_index < n:
		while left_index < right_index and a[right_index] < right_index - left_index + 1:
			left_index += 1
		num_pairs += right_index - left_index + 1
		right_index += 1
	return num_pairs
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(component) for component in input().split(' ')]
	print(solve(n, a))


def solve():
	n = int(input())
	a = input().split()
	ans = 0
	last = 0
	for i in range(n):
		if last + 1 > int(a[i]):
			ans += int(a[i])
			last = int(a[i])
		else:
			ans += last + 1
			last += 1
	print(ans)
t = int(input())
for i in range(t):
	solve()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l = 0
	r = 0
	if n == 1:
		print(1)
	else:
		for i in range(n):
			c1 = 0
			r -= l * (l + 1) // 2
			for j in range(i + l, n):
				if a[j] > l:
					l += 1
				else:
					c1 = 1
					break
			r += l * (l + 1) // 2
			l -= 1
			if c1 == 0:
				break
		print(r)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(ii) for ii in input().split()]
	if n == 1:
		print(1)
		continue
	last = 0
	ans = 0
	for i in range(n):
		if last < a[i]:
			last += 1
		else:
			last = a[i]
		ans += last
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	if n == 1:
		print(1)
		continue
	(i, res) = (1, 0)
	for k in a:
		if k >= i:
			res += i
			i += 1
		else:
			res += k
			i = k + 1
	print(res)


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	k = 1
	answer = 1
	for j in range(1, n):
		if a[j] >= k + 1:
			answer += k + 1
			k += 1
		else:
			answer += a[j]
			k = a[j]
	print(answer)


def solve(a):
	(i, j) = (0, 0)
	ans = 0
	while j < len(a):
		while j < len(a) and a[j] > j - i:
			ans += j - i + 1
			j += 1
		i += 1
	return ans

def main():
	for _ in range(int(input())):
		n = int(input())
		a = [int(e) for e in input().split()]
		print(solve(a))
main()