Read problem statements in [Mandarin], [Russian], and [Vietnamese] as well.

An index of an array is called a fixed point if the value on the index of the array is equal to the index itself. Formally, an index i of an array A of length N is a fixed point if A_{i} = i, where 1≤ i ≤ N.

For example, in the array A = [1, 3, 3, 4, 1], the indices 1, 3, 4 are fixed points.

Chef has an array A consisting of N integers. Chef tries to find the number of fixed points over all subarrays of the array A. More formally, for every pair (L, R) such that 1 ≤ L ≤ R ≤ N, Chef considers the subarray A_{L}, A_{L+1}, \dots, A_{R} and calculates the total number of fixed points in all such subarrays. However, Chef finds this task very hard. Can you help him find the number of fixed points over all subarrays?

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

- The first line contains T denoting the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N, denoting the length of the array.
- The second line contains N space-separated integers A_{1}, A_{2}, \dots, A_{N}, denoting the given array.

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

For each test case, print a single line containing one integer - the number of fixed points over all subarrays.

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

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

------ subtasks ------ 

Subtask 1 (100 points): Original constraints

----- Sample Input 1 ------ 
3
2
1 2
3
2 3 2
4
1 3 4 2

----- Sample Output 1 ------ 
3
1
5

----- explanation 1 ------ 
Let, $A[L, R]$ denotes the subarray consisting of integers from index $L$ to index $R$ of the array $A$(i.e $A_{L}, A_{L+1}, \dots, A_{R}$).

Test case $1$: 
- In the subarray $A[1, 1] = [1]$, the number of fixed points is $1$.
- In the subarray $A[1, 2] = [1, 2]$, the number of fixed points is $2$.
- In the subarray $A[2, 2] = [2]$, there is no fixed point.

Hence the total fixed points over all subarrays $= 1 + 2 + 0 = 3$.

Test case $2$: In the subarray $A[2, 3] = [3, 2]$, the second index is a fixed point. There is no fixed point in any other subarrays.

Difficulty: HARD
Tags: Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	sum = 0
	for j in range(N):
		if A[j] <= j + 1:
			sum += N - j
	print(sum)


def solve(arr):
	result = 0
	for (i, val) in enumerate(arr, 1):
		if val > i:
			continue
		result += len(arr) - i + 1
	return result

def main():
	for _ in range(int(input())):
		N = int(input())
		arr = [int(val) for val in input().split()]
		result = solve(arr)
		print(result)
main()


for _ in range(int(input())):
	length = int(input())
	arr = list(map(int, input().split()))
	counter = 0
	for (index, value) in enumerate(arr):
		if index + 1 >= value:
			counter += length - index
	print(counter)


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


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


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


t = int(input())
for _ in range(t):
	N = int(input())
	Arr = [int(x) for x in input().split()]
	ans = 0
	for i in range(N):
		if Arr[i] <= i + 1:
			ans += N - i
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(sum([n - k for (k, v) in enumerate(l) if v <= k + 1]))


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


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


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	fixed_count = 0
	for (i, j) in enumerate(a):
		if j <= i + 1:
			fixed_count += n - i
	print(fixed_count)


def main():
	for _ in range(int(input())):
		input()
		ans = 0
		arr = [int(i) for i in input().split()]
		for n in range(len(arr)):
			if n + 1 >= arr[n]:
				ans += len(arr) - (n + 1) + 1
		print(ans)
main()


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


from sys import stdin
input = stdin.readline

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


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


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


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


T = int(input())
for i in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	for j in range(len(a)):
		if a[j] <= j + 1:
			count += len(a) - j
	print(count)


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


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


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

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

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

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

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

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	n = inp()
	l = li()
	ans = 0
	for i in range(n):
		if l[i] == 1:
			ans += n - i
		elif i >= l[i] - 1:
			ans += n - i
	pr(ans)
for _ in range(inp()):
	solve()


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


for _ in range(int(input())):
	a = int(input())
	b = [int(i) for i in input().split()]
	sum = 0
	for i in range(1, 1 + a):
		if i >= b[i - 1]:
			sum += a - i + 1
	print(sum)


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


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


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


from collections import deque, defaultdict
from math import sqrt, ceil, factorial, floor, inf, log2, sqrt, gcd
import bisect
import copy
from itertools import combinations
import sys
import heapq

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

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

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	a = get_array()
	ans = 0
	for i in range(len(a)):
		if i - a[i] + 1 >= 0:
			ans += n - i
	print(ans)


def func(N, arr):
	c = 0
	for i in range(N):
		if i + 1 >= arr[i]:
			c = c + N - i
	return c
T = int(input())
for i in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	print(func(N, arr))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	cnt = 0
	for (j, val) in enumerate(l, start=1):
		if val <= j:
			cnt += n + 1 - j
		else:
			pass
	print(cnt)


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


test = int(input())
for i in range(test):
	n = int(input())
	lol = list(map(int, input().split()))
	x = 0
	for j in range(len(lol)):
		v = lol[j]
		r = j + 1
		if r >= v:
			x += n - r + 1
	print(x)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(1):
		b = a[i:n]
		for j in range(len(b)):
			if b[j] == j + 1:
				ans += 1 * (len(b) - j)
			elif b[j] <= j + 1:
				ans += 1 * (len(b) - j)
	print(ans)


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


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


T = int(input())
for o in range(T):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	for j in range(n):
		if l[j] == j + 1:
			c = c + n - j
		elif l[j] < j + 1:
			c = c + n - j
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	for j in range(n):
		if a[j] == j + 1:
			c = c + n - j
		elif a[j] < j + 1:
			c = c + n - j
	print(c)


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


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


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


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


t = int(input())
while t > 0:
	n = int(input())
	ar = list(map(int, input().split()))
	dp = [0] * n
	if ar[0] == 1:
		dp[0] = 1
	for i in range(1, n):
		if ar[i] <= i + 1:
			dp[i] += dp[i - 1] + 1
		else:
			dp[i] = dp[i - 1]
	s = 0
	for i in dp:
		s += i
	print(s)
	t -= 1


import sys
import numpy as np
input = sys.stdin.readline

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

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

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

def ist():
	return input()
T = ii()
for _ in range(T):
	n = ii()
	a = il()
	b = [0] * n
	for i in range(1, n + 1):
		if a[i - 1] <= i:
			b[i - 1] = n - i + 1
	print(sum(b))


T = int(input())
for i in range(T):
	N = int(input())
	arr = map(int, input().split())
	ss = 0
	for (idx, n) in enumerate(arr):
		if idx + 1 >= n:
			ss += N - (idx + 1) + 1
	print(ss)


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


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


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


T = int(input())
for i in range(T):
	L = int(input())
	X = input().split()
	AR = list(map(int, X))
	ans = 0
	for j in range(L):
		if AR[j] <= j + 1:
			ans = ans + L - j
	print(ans)


def process(arr, N):
	c = 0
	for i in range(N):
		if arr[i] in range(1, i + 2):
			c += N - i
	return c
for _ in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	print(process(arr, N))


import math
from collections import OrderedDict
t = int(input())
while t > 0:
	n = int(input())
	inp = input()
	a = list(map(int, inp.split(' ')))
	f = []
	for i in range(0, n):
		f.append(0)
	for i in range(0, n):
		f[i] = -1 * a[i] + i + 1
	ans = 0
	for i in range(0, n):
		count = 0
		if f[i] >= 0 and f[i] <= i:
			count += n - i
		ans += count
	print(ans)
	t -= 1


for i in range(int(input())):
	n = int(input())
	k = list(map(int, input().split()))
	total = 0
	for j in range(n):
		h = j + 1
		if h < k[j]:
			continue
		total += n - j
	print(total)


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


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


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = [int(x) for x in input().split()]
	ans = 0
	for i in range(n):
		if a[i] > i + 1:
			continue
		else:
			ans += n - i
	print(ans)


try:
	for i in range(int(input())):
		n = int(input())
		a = [int(i) for i in input().split()]
		c = 0
		for i in range(n):
			if a[i] in range(1, i + 2):
				c += n - i
		print(c)
except EOFError:
	print(0)


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


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


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


def main():
	for t in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		total = 0
		new = []
		for (i, j) in enumerate(arr, start=1):
			if i >= j:
				new.append(total + 1)
				total += 1
			else:
				new.append(total)
		print(sum(new))
main()


for i in range(int(input())):
	n = int(input())
	a = [int(k) for k in input().split()]
	z = []
	l = 0
	for k in range(n):
		if a[k] <= k + 1:
			z.append(k)
	for m in z:
		l = l + n - m
	print(l)


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


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


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


t = int(input())
for i in range(0, t):
	n = int(input())
	count = 0
	l = [int(i) for i in input().split()]
	l_2 = []
	for i in range(0, n):
		l_2.append([l[i], i + 1])
	for i in range(0, n):
		if l_2[i][0] <= l_2[i][1]:
			count += n - i
	print(count)


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


try:
	test_cases = int(input())
	for i in range(0, test_cases):
		count = 0
		l = int(input())
		A = input().split()
		for i in range(0, l):
			number = int(A[i])
			index = i + 1
			if index >= number:
				count = count + l - index + 1
		print(count)
except:
	pass


t = int(input())
for _ in range(t):
	n = int(input())
	arr = input()
	arr = arr.split(' ')
	ans = 0
	for i in range(1, len(arr) + 1):
		val = int(arr[i - 1])
		if i - val + 1 > 0:
			ans += n - i + 1
	print(ans)