You are given an array A of length N.

Determine the count of subarrays of A which contain their length as an element.

Formally, count the number of pairs (L, R) (1≤ L≤ R≤ N) such that: (R-L+1) \in \{A_{L}, A_{L+1}, \ldots, A_{R}\}.

------ Input Format ------ 

- First line will contain T, number of test cases. Then the test cases follow.
- First line of each test case contains an integer N denoting the length of the array A.
- Second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N} - denoting the array A.

------ Output Format ------ 

For each test case, output the count of subarrays containing their lengths.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 2 \cdot 10^{5}$
$1 ≤ A_{i} ≤ N$
- Sum of $N$ over all test cases does not exceed $5 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
3
1 2 1
5
2 3 1 3 5
10
10 7 4 4 2 9 2 1 9 3

----- Sample Output 1 ------ 
4
6
15

----- explanation 1 ------ 
Test Case $1$: There are $4$ subarrays $(i,j)$ containing their lengths. They are $(1,1), (1,2), (2,3),$ and $(3,3)$.

Test Case $2$: There are $6$ subarrays $(i,j)$ containing their lengths. They are $(1,2), (1,3), (1,5), (2, 4), (3,3),$ and $(3,5)$.

Difficulty: MEDIUM_HARD
Tags: Implementation

Starter code:

Solutions:
for t in range(int(input())):
	n = int(input())
	x = n + 1
	arr = list(map(int, input().split()))
	ans = [[-1] for i in range(x)]
	for i in range(n):
		ans[arr[i]] += [i]
	arr = n * x // 2
	for i in range(1, x):
		ans[i] += [n]
		arr -= sum((max(0, ans[i][j + 1] - ans[i][j] - i) for j in range(len(ans[i]) - 1)))
	print(arr)


t = int(input())
for i in range(t):
	n = int(input())
	m = n + 1
	a = list(map(int, input().split()))
	p = [[-1] for i in range(m)]
	for i in range(n):
		p[a[i]] += [i]
	a = n * m // 2
	for i in range(1, m):
		p[i] += [n]
		a -= sum((max(0, p[i][j + 1] - p[i][j] - i) for j in range(len(p[i]) - 1)))
	print(a)


ans = []
for _ in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	last = [-1] * N
	an = 0
	for i in range(N):
		s = max(0, i + 1 - A[i], 1 + last[A[i] - 1])
		e = min(N - 1, i + A[i] - 1)
		an += max(0, e - s - A[i] + 2)
		last[A[i] - 1] = i
	ans.append(an)
print(*ans, sep='\n')


t = int(input())
while t:
	n = int(input())
	inp = list(map(int, input().split()))
	myList = []
	for i in range(0, n):
		myList.append((inp[i], i + 1))
	myList = sorted(myList, key=lambda element: (element[0], element[1]))
	ans = 0
	i = 0
	while i < n:
		firsti = i
		secondi = i
		while secondi < n:
			if secondi + 1 == n:
				break
			if myList[secondi + 1][0] != myList[i][0]:
				break
			if myList[secondi + 1][1] - myList[secondi][1] >= myList[i][0]:
				break
			secondi += 1
		firstindex = max(myList[i][1] - myList[i][0] + 1, 1)
		secondindex = min(myList[secondi][1] + myList[secondi][0] - 1, n)
		ans += secondindex - firstindex - myList[i][0] + 2
		i = secondi + 1
	print(f'{ans}')
	t -= 1


def appending(fil, lis, x):
	for i in range(x):
		fil[lis[i]] += [i]
	return fil

def final(x, fill, add):
	for i in range(1, x + 1):
		fill[i] += [x]
		add = add - sum((max(0, fill[i][s + 1] - fill[i][s] - i) for s in range(len(fill[i]) - 1)))
	return add

def execute():
	for _ in range(int(input())):
		x = int(input())
		lis = list(map(int, input().split()))
		add = x * (x + 1) // 2
		fil = []
		for li in range(0, x + 1, 1):
			fil.append([-1])
		fill = appending(fil, lis, x)
		print(final(x, fill, add))
execute()


for _ in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	visit = dict()
	ans = 0
	for (i, n) in enumerate(arr):
		if n == 1:
			ans += 1
		else:
			right = min(N - n, i)
			left = max(0, i - (n - 1))
			ans += right - left + 1
			if n in visit:
				ans -= max(visit[n] - left + 1, 0)
			visit[n] = right
	print(str(ans))


T = int(input())
for _ in range(T):
	N = int(input())
	nums = list(map(int, input().split()))
	visited = dict()
	answer = 0
	for (index, num) in enumerate(nums):
		if num == 1:
			answer += 1
		else:
			right = min(N - num, index)
			left = max(0, index - (num - 1))
			answer += right - left + 1
			if num in visited:
				answer -= max(visited[num] - left + 1, 0)
			visited[num] = right
	print(str(answer))


def solve(n, arr):
	res = 0
	last_seen = {}
	for i in range(n):
		left = i - max(0, i - arr[i] + 1)
		right = min(n - 1, i + arr[i] - 1) - i
		if arr[i] in last_seen and last_seen[arr[i]] >= i - arr[i] + 1:
			left = i - last_seen[arr[i]] - 1
		size = left + right + 1
		if size >= arr[i]:
			res += size - arr[i] + 1
		last_seen[arr[i]] = i
	return res
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(n, arr))


import math

def func(n, a):
	res = 0
	lastvistart = {i: -1 for i in range(1, n + 1)}
	for i in range(n):
		start = max(0, i - a[i] + 1)
		end = min(i, n - a[i])
		start = max(lastvistart[a[i]] + 1, start)
		lastvistart[a[i]] = end
		res += end - start + 1
	return res
q = int(input())
for i in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	print(func(n, a))


t = int(input())
for tc in range(t):
	x = int(input())
	a = list(map(int, input().split()))
	res = 0
	z = [-1] * (x + 1)
	for i in range(x):
		l = max(z[a[i]] + 1, i - a[i] + 1)
		r = min(i, x - a[i])
		z[a[i]] = i
		if r >= l:
			res += r - l + 1
	print(res)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	dic = defaultdict(list)
	for (i, x) in enumerate(l):
		dic[x].append(i)
	ans = 0
	for x in dic:
		if x > n:
			continue
		if x == 1:
			ans += len(dic[x])
			continue
		a = dic[x]
		for i in range(len(a)):
			if i != 0:
				left = max(0, a[i] - a[i - 1] - 1)
			else:
				left = a[i]
			left = min(left, x - 1)
			right = min(x - 1, n - 1 - a[i])
			if left == x or right == x:
				cnt = 1 + min(left, right)
				ans += cnt
			elif left + right + 1 >= x:
				cnt = left + right + 1 - x + 1
				ans += cnt
	print(ans)


def solve():
	count = 0
	visited = set()
	last = {}
	for ele in lst:
		last[ele] = 0
	for i in range(1, n + 1):
		val = lst[i - 1]
		l_bound = max(last[val] + 1, i - val + 1)
		r_bound = min(i, n - val + 1)
		last[val] = i
		if r_bound >= l_bound:
			count += r_bound - l_bound + 1
	print(count)
t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	solve()


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


t = int(input())
while t:
	t -= 1
	n = int(input())
	li = list(map(int, input().split()))
	ans = 0
	prev = [-1] * n
	for i in range(n):
		if i - li[i] + 1 >= 0:
			st = i - li[i] + 1
		else:
			st = 0
		if prev[li[i] - 1] != -1 and prev[li[i] - 1] >= st:
			st = prev[li[i] - 1] + 1
		if st + li[i] - 1 < n:
			en = st + li[i] - 1
		else:
			en = n - 1
		if en - st + 1 == li[i] and st <= en:
			ans += min(i - st + 1, n - en)
		prev[li[i] - 1] = i
	print(ans)


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


j = int(input())
for o in range(j):
	number = int(input())
	l = [int(a) for a in input().split()]
	c = [[-1] for i in range(number + 1)]
	for i in range(number):
		c[l[i]] += [i]
	h = number * (number + 1) // 2
	reslt = h
	for i in range(1, number + 1):
		c[i] += [number]
		reslt -= sum((max(0, c[i][j + 1] - c[i][j] - i) for j in range(len(c[i]) - 1)))
	print(reslt)


try:
	for i in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		ladoo = 0
		cutoo = set()
		nary = {}
		for i in range(n):
			if l[i] not in nary.keys():
				nary[l[i]] = []
			if i - l[i] + 1 < 0:
				if i + l[i] - 1 <= n - 1:
					nary[l[i]].append([0, i + 1])
				else:
					nary[l[i]].append([0, n - l[i] + 1])
			elif i + l[i] - 1 <= n - 1:
				nary[l[i]].append([i - l[i] + 1, i + 1])
			else:
				nary[l[i]].append([i - l[i] + 1, i - l[i] + 1 + n - i])
		ladoo = 0
		for i in nary.keys():
			l = nary[i]
			ladoo += l[0][1] - l[0][0]
			for t in range(1, len(l)):
				if l[t][0] >= l[t - 1][1]:
					ladoo += l[t][1] - l[t][0]
				else:
					ladoo += l[t][1] - l[t - 1][1]
		print(ladoo)
except Exception as e:
	pass


tests = int(input())
for t0 in range(tests):
	n = int(input())
	arr = [int(i) for i in input().split()]
	counts = 0
	pairs = dict()
	for i in range(n):
		n1 = arr[i]
		s = max(0, i + 1 - n1)
		if arr[i] in pairs:
			if pairs[arr[i]] >= s:
				s = pairs[arr[i]] + 1
		if s + n1 - 1 >= n:
			s1 = n - 1
		else:
			s1 = s + n1 - 1
		if s1 - s + 1 != n1 or s > s1:
			continue
		else:
			pairs[arr[i]] = i
		counts += min(n - s1, 1 + i - s)
	print(counts)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	count = 0
	dict_count = {}
	for idx in range(n):
		sub_len = arr[idx]
		start_idx = 0
		if idx - sub_len + 1 >= 0:
			start_idx = idx - sub_len + 1
		if arr[idx] in dict_count and dict_count[arr[idx]] >= start_idx:
			start_idx = dict_count[arr[idx]] + 1
		end_idx = start_idx + sub_len - 1
		if start_idx + sub_len - 1 > n:
			end_idx = n - 1
		if end_idx - start_idx + 1 != sub_len or start_idx > end_idx:
			continue
		count += min(idx - start_idx + 1, n - end_idx)
		dict_count[arr[idx]] = idx
	print(count)


t1 = int(input())
for i in range(t1):
	n1 = int(input())
	l = list(map(int, input().split()))
	x = []
	for y in range(n1 + 1):
		x += [[-1]]
	for j in range(n1):
		x[l[j]] += [j]
	z = n1 * (n1 + 1) // 2
	for j in range(1, n1 + 1):
		x[j] += [n1]
		for k in range(len(x[j]) - 1):
			z -= max(0, x[j][k + 1] - x[j][k] - j)
	print(z)


for _ in range(int(input())):
	n = int(input())
	m = n + 1
	lst = list(map(int, input().split()))
	arr = [[-1] for i in range(m)]
	for i in range(n):
		arr[lst[i]] += [i]
	lst = n * m // 2
	for i in range(1, m):
		arr[i] += [n]
		lst -= sum((max(0, arr[i][j + 1] - arr[i][j] - i) for j in range(len(arr[i]) - 1)))
	print(lst)


import numpy as np

def subarray_len():
	input()
	arr = list(map(int, input().split()))
	indexed_elems = {}
	for (i, elem) in enumerate(arr):
		indexed_elems.setdefault(elem, list()).append(i)
	count = 0
	for elem in indexed_elems.keys():
		last_left = 0
		for i in indexed_elems[elem]:
			r = min(len(arr), i + elem)
			l = max(last_left, i - elem + 1)
			count += max(0, r - elem + 1 - l)
			last_left = i + 1
	return count

def submission():
	t = int(input())
	for i in range(t):
		print(subarray_len())
submission()


tests = int(input())
for i in range(tests):
	n = int(input())
	ls = list(map(int, input().split()))
	dis = {}
	cos = 0
	for i in range(0, n):
		a = ls[i]
		l = i - a + 1
		r = a + i - 1
		car = 0
		if a in dis:
			if l <= dis[a]:
				car = l - (dis[a] + 1)
				l = dis[a] + 1
		sm = a + car
		if l < 0:
			sm = sm + l
		if r > n - 1:
			sm = sm - (r - (n - 1))
		if sm > 0:
			cos = cos + sm
		dis[a] = i
	print(cos)


for test in range(int(input())):
	number = int(input())
	mass = number + 1
	array = list(map(int, input().split()))
	pas = [[-1] for i in range(mass)]
	for i in range(number):
		pas[array[i]] += [i]
	array = number * mass // 2
	for i in range(1, mass):
		pas[i] += [number]
		array -= sum((max(0, pas[i][j + 1] - pas[i][j] - i) for j in range(len(pas[i]) - 1)))
	print(array)


def binary_search(arr, low, high, x):
	if high >= low:
		mid = (high + low) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] > x:
			return binary_search(arr, low, mid - 1, x)
		else:
			return binary_search(arr, mid + 1, high, x)
	else:
		return -1
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	d = dict()
	maxi = binary_search(l, 0, n - 1, 12)
	ans = 0
	for i in range(n):
		(s, new_size) = (l[i], None)
		if i - s + 1 >= 0:
			new_size = i - s + 1
		else:
			new_size = 0
		if l[i] in d and d.get(l[i]) >= new_size:
			new_size = d.get(l[i]) + 1
		a = None
		if new_size + s - 1 < n:
			a = new_size + s - 1
		else:
			a = n - 1
		if a - new_size + 1 != s or new_size > a:
			continue
		ans = ans + min(i - new_size + 1, n - a)
		d[l[i]] = i
	print(ans)


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


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	long = len(lst)
	dic = {}
	times = 0
	toremove = 0
	for l in range(n):
		item_lst = dic.get(lst[l], None)
		if item_lst is None:
			item_lst = [l]
			dic[lst[l]] = item_lst
		else:
			item_lst.append(l)
	for (key, items) in dic.items():
		times = times + key * len(items)
		for i in range(1, len(items)):
			diff = items[i] - items[i - 1]
			diff = key - diff
			if diff > 0:
				toremove = toremove + diff
		for i in range(len(items)):
			diff = key - items[i] - 1
			if diff > 0:
				toremove = toremove + diff
				break
		for i in range(len(items) - 1, -1, -1):
			diff = key - (n - items[i])
			if diff > 0:
				toremove += diff
				break
	times = times - toremove
	print(times)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	res = 0
	d = {}
	for i in range(n):
		l = a[i]
		if i - l + 1 >= 0:
			si = i - l + 1
		else:
			si = 0
		if a[i] in d and d[a[i]] >= si:
			si = d[a[i]] + 1
		if si + l - 1 >= n:
			ei = n - 1
		else:
			ei = si + l - 1
		if ei - si + 1 != l or si > ei:
			continue
		res += min(i - si + 1, n - ei)
		d[a[i]] = i
	print(res)


for _ in range(int(input())):
	c = 0
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in range(n):
		m = l[i]
		if m == 1:
			c += 1
		else:
			if m not in d:
				d[m] = i
				k = -1
			else:
				k = d[m]
				d[m] = i
			if i == k:
				f = 0
			else:
				f = i - k - 1
			j = n - i
			if f + j < m:
				continue
			c += 1
			if f == 0 or j == 1 or f + j == m:
				continue
			if f + 1 >= m and j >= m:
				c += m - 1
			else:
				c += min(f, j - 1, f + j - m)
	print(c)


for abhi in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = [[-1] for i in range(n + 1)]
	for i in range(n):
		b[a[i]] += [i]
	c = n * (n + 1) // 2
	for i in range(1, n + 1):
		b[i] += [n]
		for j in range(len(b[i]) - 1):
			c -= max(0, b[i][j + 1] - b[i][j] - i)
	print(c)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	m = {}
	ans = 0
	for i in range(n):
		sI = max(0, i - arr[i] + 1)
		if arr[i] in m and m[arr[i]] >= sI:
			sI = m[arr[i]] + 1
		eI = min(n - 1, sI + arr[i] - 1)
		if eI - sI + 1 != arr[i]:
			continue
		ans += min(i - sI + 1, n - eI)
		m[arr[i]] = i
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	ans = 0
	dict = {}
	for i in range(n):
		le = arr[i]
		si = max(i - le + 1, 0)
		if le in dict.keys() and dict[le] >= si:
			si = dict[le] + 1
		ei = min(si + le - 1, n - 1)
		if ei - si + 1 != le or si > ei:
			continue
		ans += min(i - si + 1, n - ei)
		dict[le] = i
	print(ans)


def solution():
	n = int(input())
	l = list(map(int, input().split(' ')))
	a = [[-1] for i in range(n + 1)]
	for i in range(n):
		a[l[i]] += [i]
	s = n * (n + 1) // 2
	for i in range(1, n + 1):
		a[i] += [n]
		s -= sum((max(0, a[i][j + 1] - a[i][j] - i) for j in range(len(a[i]) - 1)))
	print(s)
for i in range(int(input())):
	solution()


try:
	t = int(input())
	for i in range(t):
		n = int(input())
		a = [int(a) for a in input().split()]
		c = 0
		d = {}
		for j in range(0, n):
			l = j - a[j] + 1
			if l < 0:
				l = 0
			if (a[j] in d) == True and l <= d[a[j]]:
				l = d[a[j]] + 1
			r = l + a[j] - 1
			if r >= n:
				r = n - 1
			if r - l + 1 == a[j]:
				c = c + min(j - l + 1, n - r)
			d[a[j]] = j
		print(c)
except:
	pass


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	prev_index = [-1] * (2 * 10 ** 5 + 1)
	for i in range(n):
		j = i
		if prev_index[arr[i]] != -1:
			ref = n - 1 - prev_index[arr[i]]
			j = j - (prev_index[arr[i]] + 1)
		else:
			ref = n
		value = 0
		if ref - arr[i] >= 0:
			left = j + 1
			right = ref - 1 - j + 1
			if left <= arr[i] or right <= arr[i]:
				value = min(left, right)
			else:
				value = arr[i]
			if ref - arr[i] + 1 < arr[i]:
				value = min(value, ref - arr[i] + 1)
		ans += value
		prev_index[arr[i]] = i
	print(ans)


for tc in range(int(input())):
	p = int(input())
	arr = list(map(int, input().split()))
	r = p + 1
	t = [[-1] for i in range(r)]
	for i in range(p):
		t[arr[i]] += [i]
	arr = p * r // 2
	for i in range(1, r):
		t[i] += [p]
		arr -= sum((max(0, t[i][j + 1] - t[i][j] - i) for j in range(len(t[i]) - 1)))
	print(arr)


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	array = input().split()
	Count = 0
	dic = {}
	for i in range(0, n):
		len = int(array[i])
		Subarray_index1 = i - len + 1 if i - len + 1 >= 0 else 0
		if int(array[i]) in dic.keys() and dic[int(array[i])] >= Subarray_index1:
			Subarray_index1 = dic[int(array[i])] + 1
		Subarray_index2 = n - 1 if Subarray_index1 + len - 1 >= n else Subarray_index1 + len - 1
		if Subarray_index2 - Subarray_index1 + 1 != len or Subarray_index1 > Subarray_index2:
			continue
		Count += min(i + 1 - Subarray_index1, n - Subarray_index2)
		dic[int(array[i])] = i
	print(Count)


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


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	dummy_array = [[-1] for i in range(n + 1)]
	for i in range(n):
		if i < 0:
			break
		dummy_array[A[i]] += [i]
	A = n * (n + 1) // 2
	for i in range(1, n + 1):
		dummy_array[i] += [n]
		A -= sum((max(0, dummy_array[i][j + 1] - dummy_array[i][j] - i) for j in range(len(dummy_array[i]) - 1)))
	print(A)


for testcase in range(int(input())):
	n = int(input())
	cnt = n + 1
	harshal = list(map(int, input().split()))
	rrr = [[-1] for i in range(cnt)]
	for i in range(n):
		rrr[harshal[i]] += [i]
	harshal = n * cnt // 2
	for i in range(1, cnt):
		rrr[i] += [n]
		harshal -= sum((max(0, rrr[i][j + 1] - rrr[i][j] - i) for j in range(len(rrr[i]) - 1)))
	print(harshal)


from collections import defaultdict

def overlap(d, n, var):
	for (i, j) in d.items():
		t = d[i][0]
		for k in range(1, len(j)):
			if d[i][k] - t <= i - 1:
				cur = d[i][k] - 1 - min(d[i][k] - 1, i - 1)
				var += min(min(t - 1 - cur, i - 1), n - (cur + i - 1))
				if t - 1 + i - 1 < n:
					var += 1
			t = d[i][k]
	return var
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = defaultdict(list)
	for i in range(n):
		d[a[i]].append(i + 1)
	ans = 1
	for i in range(1, n):
		temp = 0
		if a[i] == 1:
			temp += 1
		else:
			cur = i - min(i, a[i] - 1)
			temp += min(min(i, a[i] - 1), n - (cur + a[i] - 1))
			if i + a[i] - 1 < n:
				temp += 1
		ans += temp
	print(ans - overlap(d, n, 0))


t = int(input())
while t > 0:
	n = int(input())
	arr = [int(x) for x in input().split()]
	f1 = []
	d = {}
	ans = 0
	for i in range(0, n):
		num = arr[i]
		newindex = i + 1
		st = max(1, newindex - num + 1)
		en = min(n, newindex + num - 1)
		if num in d.keys() and newindex - d[num] < num:
			st = d[num] + 1
		if en - st + 1 < num:
			continue
		curr = en - st + 1 - num + 1
		ans += curr
		d[num] = newindex
	print(ans)
	t -= 1


for testcase in range(int(input())):
	n = int(input())
	m = n + 1
	a = list(map(int, input().split()))
	dp = [[-1] for i in range(m)]
	for i in range(n):
		dp[a[i]] += [i]
	a = n * m // 2
	for i in range(1, m):
		dp[i] += [n]
		a -= sum((max(0, dp[i][j + 1] - dp[i][j] - i) for j in range(len(dp[i]) - 1)))
	print(a)


for i in range(int(input())):
	n = int(input())
	some = list(map(int, input().split()))
	a = n + 1
	g = [[-1] for j in range(a)]
	for j in range(n):
		g[some[j]] += [j]
	some = n * a // 2
	for i in range(1, a):
		g[i] += [n]
		some -= sum((max(0, g[i][j + 1] - g[i][j] - i) for j in range(len(g[i]) - 1)))
	print(some)


def subarraay_len(n: int, num: list) -> int:
	max_total = 0
	memo = {}
	for (index, ele) in enumerate(num):
		total = ele
		count_to_reduce = 0
		if ele in memo:
			diff = index - memo[ele]
			if diff < ele:
				count_to_reduce += ele - diff
		elif index < ele - 1:
			count_to_reduce += ele - 1 - index
		memo[ele] = index
		if n - index < ele:
			count_to_reduce += ele - (n - index)
		total -= count_to_reduce
		max_total += max(total, 0)
	return max_total

def main():
	test = int(input())
	for _ in range(test):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		print(subarraay_len(n, arr))
main()


for x in range(int(input())):
	n = int(input())
	z = n + 1
	a = list(map(int, input().split()))
	q = [[-1] for i in range(z)]
	for x1 in range(n):
		q[a[x1]] += [x1]
	a = n * z // 2
	for y in range(1, z):
		q[y] += [n]
		a -= sum((max(0, q[y][j + 1] - q[y][j] - y) for j in range(len(q[y]) - 1)))
	print(a)


from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ct = 0
	d = defaultdict(lambda : -1)
	for p in range(n):
		v = a[p]
		f = d[v]
		if f == -1:
			f = 0
		else:
			f = f + 1
		z1 = min(0, p - f - v + 1)
		z2 = min(0, n - 1 - p - v + 1)
		ct += v + max(-v, z1 + z2)
		d[v] = p
	print(ct)


def main():
	for _ in range(int(input())):
		N = int(input())
		values = [int(x) for x in input().split(' ')]
		HM = dict()
		ans = 0
		for i in range(N):
			lenArr = values[i]
			if i - lenArr + 1 >= 0:
				si = i - lenArr + 1
			else:
				si = 0
			if values[i] in HM.keys() and HM[values[i]] >= si:
				si = HM[values[i]] + 1
			if si + lenArr - 1 >= N:
				ei = N - 1
			else:
				ei = si + lenArr - 1
			if ei - si + 1 != lenArr or si > ei:
				continue
			ans += min(i - si + 1, N - ei)
			HM[values[i]] = i
		print(ans)
main()


from collections import Counter, deque, defaultdict, namedtuple
from math import *
from random import randint
import itertools

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	d = defaultdict(int)
	for i in range(n):
		start = max(d[a[i]], i - a[i] + 1)
		end = min(a[i] + i - 1, n - 1)
		if end - start + 1 >= a[i]:
			ans += max(0, end - start + 1 - a[i]) + 1
		d[a[i]] = i + 1
	print(ans)
testCases = int(input())
for i in range(testCases):
	solve()


for _ in range(int(input())):
	num = int(input())
	inp = list(map(int, input().split()))
	par = num + 1
	x = [[-1] for i in range(par)]
	for i in range(num):
		x[inp[i]] += [i]
	yes = num * par // 2
	for i in range(1, par):
		x[i] += [num]
		yes -= sum((max(0, x[i][j + 1] - x[i][j] - i) for j in range(len(x[i]) - 1)))
	print(yes)


T = int(input())
while T > 0:
	n = int(input())
	lst = input().split()
	count = 0
	dic = {}
	for i in range(n):
		if lst[i] in dic and dic[lst[i]] + int(lst[i]) > i:
			si = dic[lst[i]] + 1
			ei = si + int(lst[i]) - 1
		elif int(lst[i]) - 1 >= i:
			si = 0
			ei = int(lst[i]) - 1
		else:
			si = i - int(lst[i]) + 1
			ei = i
		if ei >= n:
			continue
		l = i - si + 1
		r = n - 1 - ei + 1
		if l >= r:
			count += r
		else:
			count += l
		dic[lst[i]] = i
	print(count)
	T -= 1


for _ in range(int(input())):
	N = int(input())
	M = N + 1
	A = list(map(int, input().split()))
	S = [[-1] for i in range(M)]
	for i in range(N):
		S[A[i]] += [i]
	A = N * M // 2
	for i in range(1, M):
		S[i] += [N]
		A -= sum((max(0, S[i][j + 1] - S[i][j] - i) for j in range(len(S[i]) - 1)))
	print(A)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	diction = dict()
	count = 0
	for i in range(n):
		l = arr[i]
		if i - l + 1 >= 0:
			a = i - l + 1
		else:
			a = 0
		if arr[i] in diction and diction[arr[i]] >= a:
			a = diction[arr[i]] + 1
		if a + l - 1 >= n:
			b = n - 1
		else:
			b = a + l - 1
		if b - a + 1 != l or a > b:
			continue
		count += min(i - a + 1, n - b)
		diction[arr[i]] = i
	print(count)


from collections import *
for n in [*open(0)][2::2]:
	(a, b, c) = ([*map(int, n.split())], defaultdict(lambda : -1), 0)
	for (i, j) in enumerate(a):
		(v, b[j]) = (b[j], i)
		c += max(0, i - max(i - j + 1, v + 1) - max(0, i + j - len(a)) + 1)
	print(c)


t = int(input())
for i in range(0, t):
	N = int(input())
	M = N + 1
	A = list(map(int, input().split()))
	X = [[-1] for i in range(M)]
	for i in range(N):
		X[A[i]] += [i]
	A = N * M // 2
	for i in range(1, M):
		X[i] += [N]
		A -= sum((max(0, X[i][j + 1] - X[i][j] - i) for j in range(len(X[i]) - 1)))
	print(A)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	temp_dict = {}
	for i in range(len(a)):
		number = a[i]
		left_max = min(i, number - 1)
		right_max = min(n - i - 1, number - 1)
		if number in temp_dict:
			new_left = i - temp_dict[number] - 1
			left_max = min(left_max, new_left)
		temp_dict[number] = i
		total_window = right_max + left_max + 1
		slide = total_window - number + 1
		count += max(slide, 0)
	print(count)


for i in range(int(input())):
	input()
	was = {}
	coun = 0
	arr = [int(s) for s in input().split(' ')]
	N = len(arr)
	dic = {}
	for i in range(N):
		k = arr[i]
		l = max(i - (k - 1), 0)
		r = min(i + (k - 1), N - 1)
		if k in dic:
			if i - dic[k] < k:
				l = min(dic[k] + 1, N - 1)
		num = max(r - k + 1 - l + 1, 0)
		coun += num
		dic[k] = i
	print(coun)


for _ in range(int(input())):
	d = {}
	ans = 0
	n = int(input())
	l = list(map(int, input().split()))
	for i in range(n):
		start = i - l[i] + 1
		if start < 0:
			start = 0
		if l[i] in d and d[l[i]] >= start:
			start = d[l[i]] + 1
		end = start + l[i] - 1
		if end > n:
			end = n - 1
		if end - start + 1 != l[i] or start > end:
			continue
		ans += min(i - start + 1, n - end)
		d[l[i]] = i
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	count = 0
	hashmap = dict()
	for i in range(n):
		length = arr[i]
		if i - length + 1 >= 0:
			si = i - length + 1
		else:
			si = 0
		if arr[i] in hashmap and hashmap[arr[i]] >= si:
			si = hashmap[arr[i]] + 1
		if si + length - 1 >= n:
			ei = n - 1
		else:
			ei = si + length - 1
		if ei - si + 1 != length or si > ei:
			continue
		count += min(i - si + 1, n - ei)
		hashmap[arr[i]] = i
	print(count)