Chef has a sequence of N integers A = [A_{1}, A_{2},\dots,A_{N}]. He can perform the following operation any number of times (possibly, zero):

Choose any positive integer K and insert it at any position of the sequence (possibly the beginning or end of the sequence, or in between any two elements).

For example, if A=[5,3,4] and Chef selects K=2, then after the operation he can obtain one of the sequences [\underline{2},5,3,4], [5,\underline{2},3,4], [5,3,\underline{2},4], or [5,3,4,\underline{2}].

Chef wants this sequence to satisfy the following condition: for each 1≤ i ≤ \mid A \mid , A_{i} \neq i. Here, \mid A\mid denotes the length of A.

Help Chef to find the minimum number of operations that he has to perform to achieve this goal. It can be proved that under the constraints of the problem, it's always possible to achieve this goal in a finite number of operations.

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

- The first line of input contains an integer T, denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains an integer N.
- The second line contains N space-separated integers A_{1}, A_{2}, \dots, A_{N}.

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

For each test case, print a single line containing one integer — the minimum number of operations that Chef has to perform to achieve the given condition.

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

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

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

Subtask #1 (100 points): Original constraints

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

----- Sample Output 1 ------ 
0
1
2

----- explanation 1 ------ 
Test case $1$: The given sequence does not contain any index $i$ such that $A_{i} = i$. Hence Chef does not have to perform any operation.

Test case $2$: In the given sequence, $A_{3} = 3$. Chef can choose $K = 2$ and insert it before the first element, making the sequence $A = [\underline{2}, 4, 1, 3]$, which does not contain any index $i$ for which $A_{i} = i$.

Test case $3$: In the given sequence, $A_{2} = 2$. Chef can perform the following sequence of operations:
- Choose $K = 5$ and insert it before the first element. The sequence becomes $A = [\underline{5}, 3, 2, 4, 2]$, and now $A_{4} = 4$.
- Choose $K = 3$ and insert it between the third and fourth element. The sequence becomes  $A = [5, 3, 2, \underline{3}, 4, 2]$, which does not contain any index $i$ for which $A_{i} = i$.

It can be verified that there is no way to satisfy the given condition in less than two operations.

Difficulty: EASY
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
for p in range(int(input())):
	r = int(input())
	q = list(map(int, input().split()))
	priya = 0
	for s in range(r):
		x = s + priya + 1
		if x == q[s]:
			priya = priya + 1
	print(priya)


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


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


def check(l1, index):
	for i in range(index, len(l1)):
		if l1[i] == i + 1:
			return i
	return -1
for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	count = 0
	index = 0
	while True:
		index = check(l1, index)
		if index != -1:
			count += 1
			l1.insert(index, -1)
		if index == -1:
			break
	print(count)


class Mode:

	def __init__(self, n, arr):
		self.__n = n
		self.arr = arr

	def Solution(self):
		c = 0
		j = 1
		for i in self.arr:
			if c + j == i:
				c += 1
			j += 1
		return c

def main():
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split(' ')))[:n]
		ans = Mode(n, arr)
		print(ans.Solution())
main()


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


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


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


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


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


for _ in range(int(input())):
	N = int(input())
	A = [int(i) for i in input().split()]
	count = 0
	i = 0
	while i in range(len(A)):
		if A[i] == i + 1:
			count = count + 1
			A.insert(i, len(A) + i + count)
		i = i + 1
	print(count)


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


for tc in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	diff = 1
	count = 0
	for (i, ele) in enumerate(arr):
		if i + diff == arr[i]:
			count += 1
			diff += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	ans = 0
	i = 0
	while i < len(a):
		if a[i] == i + 1:
			a.insert(i, 0)
			ans += 1
		i += 1
	print(ans)


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


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


t = int(input())
while t != 0:
	n = int(input())
	l = list(map(int, input().split()))
	k = 0
	c = 0
	while k < n:
		if l[k] == k + 1:
			l.insert(k, k)
			n += 1
			c += 1
		k += 1
	print(c)
	t -= 1


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


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


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


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


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


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


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


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


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	i = 0
	insert_count = 0
	while i < len(A):
		if A[i] == i + 1:
			A.insert(i, (i + 1) % 10)
			insert_count += 1
			i += 1
		i += 1
	print(insert_count)


for _ in range(int(input())):
	x = int(input())
	m = list(map(int, input().split()))
	n = 0
	for i in range(x):
		h = 1 + i + n
		if h == m[i]:
			n += 1
	print(n)


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


def solve(n, lst):
	i = 0
	c = 0
	while i < n:
		if i + 1 == lst[i]:
			lst.insert(i, i + 1)
			n += 1
			c += 1
		i += 1
	print(c)
for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	solve(n, lst)


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


T = int(input())
for i in range(T):
	a = 1
	b = int(input())
	c = list(map(int, input().split()))
	for j in range(b):
		if c[j] == j + a:
			a = a + 1
	print(a - 1)


for _ in range(int(input())):
	n = int(input())
	a = [int(j) for j in input().split()]
	cnt = 1
	for i in range(n):
		if a[i] == cnt + i:
			cnt += 1
	print(cnt - 1)


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


def solve():
	n = int(input())
	a = [int(i) for i in input().split()]
	count = 1
	for i in range(n):
		if i + count == a[i]:
			count += 1
	return count - 1
for i in range(int(input())):
	print(solve())


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


t = int(input())
for i in range(t):
	n = int(input())
	l1 = list(map(int, input().split()))
	l1.insert(0, 5)
	insertion = 0
	for i in range(1, len(l1)):
		if l1[i] == i + insertion:
			insertion += 1
	print(insertion)


t = int(input())
while t:
	t = t - 1
	n = int(input())
	a = list(map(int, input().split()))
	isTrue = True
	c = 0
	coun = 0
	for i in range(0, 2 * n):
		if coun < len(a):
			if a[i] == i + 1:
				c += 1
				a.insert(i, 2 * n + 1)
			coun += 1
	print(c)


t = int(input())
while t > 0:
	n = int(input())
	t = t - 1
	x = list(map(int, input().split()))
	j = 1
	count = 0
	for i in range(n):
		if x[i] != j:
			j = j + 1
		else:
			j = j + 2
			count = count + 1
	print(count)


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


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	countt = 0
	arr = []
	inc = 0
	for i in range(len(l)):
		if l[i] == i + 1 + inc:
			inc += 1
			countt += 1
	print(countt)


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


for _ in range(int(input())):
	count = 0
	k = 1
	N = int(input())
	li_ar = list(map(int, input().split()))
	for i in range(N):
		if li_ar[i] == i + 1 + count:
			count += 1
	print(count)


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


tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	k = 0
	for j in range(length):
		if arr[j] == j + k + 1:
			k += 1
	print(k)


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


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


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


T = int(input())
for i in range(T):
	size = int(input())
	A = list(map(int, input().split()))
	op = 0
	for i in range(size):
		updated = i + op + 1
		if updated == A[i]:
			op += 1
	print(op)


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	k = 0
	for i in range(len(arr)):
		if i + 1 + k == arr[i]:
			k = k + 1
	print(k)