You are given a permutation$^\dagger$ $p$ of length $n$.

In one operation, you can choose two indices $1 \le i < j \le n$ and swap $p_i$ with $p_j$.

Find the minimum number of operations needed to have exactly one inversion$^\ddagger$ in the permutation.

$^\dagger$ A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

$^\ddagger$ The number of inversions of a permutation $p$ is the number of pairs of indices $(i, j)$ such that $1 \le i < j \le n$ and $p_i > p_j$.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$).

The second line of each test case contains $n$ integers $p_1,p_2,\ldots, p_n$ ($1 \le p_i \le n$). It is guaranteed that $p$ is a permutation.

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


-----Output-----

For each test case output a single integer — the minimum number of operations needed to have exactly one inversion in the permutation. It can be proven that an answer always exists.


-----Examples-----

Input
4
2
2 1
2
1 2
4
3 4 1 2
4
2 4 3 1
Output
0
1
3
1


-----Note-----

In the first test case, the permutation already satisfies the condition.

In the second test case, you can perform the operation with $(i,j)=(1,2)$, after that the permutation will be $[2,1]$ which has exactly one inversion.

In the third test case, it is not possible to satisfy the condition with less than $3$ operations. However, if we perform $3$ operations with $(i,j)$ being $(1,3)$,$(2,4)$, and $(3,4)$ in that order, the final permutation will be $[1, 2, 4, 3]$ which has exactly one inversion.

In the fourth test case, you can perform the operation with $(i,j)=(2,4)$, after that the permutation will be $[2,1,3,4]$ which has exactly one inversion.

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

Graph algorithms

Graph traversal

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = [0] * n
	c = 0
	for i in range(n):
		if d[a[i] - 1] == 0:
			c += 1
			t = i
			while d[t] == 0:
				d[t] = c
				t = a[t] - 1
	ans = n - c + 1
	for i in range(n - 1):
		if d[i] == d[i + 1]:
			ans -= 2
			break
	print(ans)


out = []
for _ in range(int(input())):
	n = int(input())
	p = [int(i) - 1 for i in input().split()]
	ind = 1
	ans = 0
	comp = [0] * n
	for i in range(n):
		if comp[i]:
			continue
		v = i
		while comp[v] == 0:
			comp[v] = ind
			v = p[v]
			ans += 1
		ind += 1
		ans -= 1
	for i in range(n - 1):
		if comp[i] == comp[i + 1]:
			out.append(ans - 1)
			break
	else:
		out.append(ans + 1)
for i in out:
	print(i)


def main():
	visit = [0] * n
	cnt = 0
	idx = 1
	for i in range(n):
		if visit[i]:
			continue
		j = i
		while not visit[j]:
			visit[j] = idx
			j = A[j]
			cnt += 1
		idx += 1
		cnt -= 1
	for i in range(n - 1):
		if visit[i] == visit[i + 1]:
			return cnt - 1
	return cnt + 1
t = int(input())
for case in range(t):
	n = int(input())
	A = list(map(lambda x: int(x) - 1, input().split()))
	print(main())


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	arr = [0] + arr
	visited = [-1 for i in range(n + 1)]
	yes = 0
	ans = 0
	for i in range(1, n + 1):
		if visited[i] != -1:
			continue
		temp = arr[i]
		visited[i] = i
		l = 0
		while temp != i:
			visited[temp] = i
			temp = arr[temp]
			ans += 1
	for i in range(n):
		if visited[i] == visited[i + 1]:
			yes = 1
			break
	print(ans + 1 - 2 * yes)


t = int(input())
for ___ in range(t):
	n = int(input())
	cnt = 0
	ok = False
	vis = [0] * (n + 2)
	p = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		if vis[i] > 0:
			continue
		k = i
		while True:
			vis[k] = i
			if vis[k - 1] == i or vis[k + 1] == i:
				ok = True
			k = p[k]
			if k == i:
				break
			cnt += 1
	print(cnt + (-1 if ok else 1))


def conseq(arr):
	if len(arr) == 0:
		return False
	for idx in range(len(arr) - 1):
		if arr[idx + 1] == arr[idx] + 1:
			return True

def solve():
	n = int(input())
	arr = [int(x) - 1 for x in input().split(' ')]
	vis = [False] * n
	parts = []
	conseqs = []
	created_inversion = False
	for idx in range(n):
		if idx == arr[idx]:
			vis[idx] = True
		elif vis[idx] is False:
			cidx = idx
			tarr = []
			while vis[cidx] is False:
				vis[cidx] = True
				tarr.append(cidx)
				cidx = arr[cidx]
			starr = sorted(tarr)
			tconseq = conseq(starr)
			if created_inversion is False and len(starr) == 2 and (tconseq is True):
				created_inversion = True
			else:
				parts.append(tarr)
				conseqs.append(tconseq)
	ans = 0
	for idx in range(len(parts)):
		pp = parts[idx]
		cc = conseqs[idx]
		if created_inversion is False and cc is True:
			created_inversion = True
			ans += len(pp) - 2
		else:
			ans += len(pp) - 1
	if created_inversion is False:
		ans += 1
	return ans
tc = int(input())
for idx in range(tc):
	ans = solve()
	print(ans)


t = int(input(''))
for _ in range(t):
	n = int(input(''))
	p = [int(x) - 1 for x in input('').split(' ')]
	vis = [0] * n
	turn = 1
	cost = 0
	for i in range(n):
		if not vis[i]:
			vis[i] = turn
			cur = p[i]
			ln = 1
			while cur != i:
				vis[cur] = turn
				ln += 1
				cur = p[cur]
			cost += ln - 1
			turn += 1
	adj = False
	for i in range(n - 1):
		if vis[i] == vis[i + 1]:
			adj = True
			break
	if adj:
		print(cost - 1)
	else:
		print(cost + 1)


for _ in range(int(input())):
	N = int(input())
	P = list(map(int, input().split()))
	v = [False] * N
	ans = 0
	f = False
	for i in range(N):
		if v[i]:
			continue
		v[i] = True
		cur = P[i] - 1
		gr = [i]
		while cur != i:
			v[cur] = True
			gr.append(cur)
			cur = P[cur] - 1
		gr.sort()
		cnt = len(gr) - 1
		if not f:
			for i in range(len(gr) - 1):
				if gr[i + 1] - gr[i] == 1:
					cnt -= 1
					f = True
					break
		ans += cnt
	if not f:
		ans += 1
	print(ans)


def solve(perm):
	touched = set()
	cycles = []
	for elem in range(len(perm)):
		if elem in touched:
			continue
		touched.add(elem)
		cycle = [elem]
		while perm[elem] not in touched:
			elem = perm[elem]
			touched.add(elem)
			cycle.append(elem)
		cycles.append(cycle)
	if all((len(cycle) == 1 for cycle in cycles)):
		return 1
	ans = sum((len(cycle) - 1 for cycle in cycles))
	for cycle in cycles:
		s = set(cycle)
		for elem in s:
			if elem + 1 in s:
				return ans - 1
	return ans + 1

def run():
	n = int(input())
	p = [int(x) - 1 for x in input().split()]
	ans = solve(p)
	print(ans)
tests_nr = int(input())
for _ in range(tests_nr):
	run()


import math
from collections import defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop, heapify

def getList(val=0):
	if not val:
		return list(map(int, input().split()))
	else:
		return list(map(str, input().split()))

def getTuple(val=0):
	if not val:
		return map(int, input().split())
	return map(str, input().split())

def printList(arr):
	for i in arr:
		print(i, end=' ')
	print()

def myCode():
	n = int(input())
	arr = getList()
	dct = defaultdict(int)
	now = 0
	arrType = [-1 for i in arr]
	total = 0
	for i in range(1, n + 1):
		if arrType[i - 1] + 1:
			continue
		j = i
		while arrType[j - 1] == -1:
			arrType[j - 1] = now
			dct[now] += 1
			j = arr[j - 1]
		total += dct[now] - 1
		now += 1
	ans = float('inf')
	for i in range(n - 1):
		if arrType[i] == arrType[i + 1]:
			ans = min(ans, total - 1)
		else:
			ans = min(ans, total + 1)
	print(ans)
for _ in range(int(input())):
	myCode()


t = int(input())
for _ in range(t):
	n = int(input())
	L = list(map(int, input().split()))
	a = 0
	Visited = [False] * n
	C = []
	f = False
	for i in range(n):
		if not Visited[i]:
			if L[i] == i + 1:
				Visited[i] = True
			else:
				c = 1
				j = i
				K = [i]
				Visited[j] = True
				while L[j] != i + 1:
					j = L[j] - 1
					K.append(j)
					Visited[j] = True
					c += 1
				C.append(c)
				K.sort()
				for i in range(1, len(K)):
					if K[i] == K[i - 1] + 1:
						f = True
						break
	ans = 0
	for i in range(len(C)):
		ans += C[i] - 1
	if f:
		ans -= 1
	else:
		ans += 1
	print(ans)


def cnt_cc(lst):
	cc_id = [None] * len(lst)
	cnt = 0
	for i in range(len(lst)):
		if cc_id[i] is not None:
			continue
		cnt += 1
		top = i
		while cc_id[top] is None:
			cc_id[top] = cnt
			top = lst[top]
	return (cnt, cc_id)
t = int(input())
for _ in range(t):
	n = int(input())
	lst = [int(v) - 1 for v in input().strip().split()]
	backward = [None] * len(lst)
	for (i, v) in enumerate(lst):
		backward[v] = i
	(total_cc, cc_id) = cnt_cc(lst)
	answer = 1000000000.0
	for i in range(1, len(lst)):
		if cc_id[backward[i]] != cc_id[backward[i - 1]]:
			cur_cc = total_cc - 1
		else:
			cur_cc = total_cc + 1
		answer = min(answer, n - cur_cc)
	print(answer)


t = int(input())
for _ in range(t):
	n = int(input())
	ls = list(map(int, input().split()))
	done = [0] * n
	bns = -1
	cct = 0
	for i in range(n):
		if done[i] == 0:
			j = i
			k = ls[i] - 1
			cycle = set()
			cycle.add(j)
			cycle.add(k)
			while i != ls[j] - 1:
				cct += 1
				done[k] = 1
				j = k
				k = ls[k] - 1
				cycle.add(k)
			sorted_cyc = sorted(cycle)
			len_cyc = len(sorted_cyc)
			for j in range(len_cyc - 1):
				if sorted_cyc[j + 1] - 1 == sorted_cyc[j]:
					bns = 1
	print(cct - bns)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	done = [False] * n
	adj = False
	cnt = 0
	for i in range(n):
		if done[i] or arr[i] == i + 1:
			continue
		else:
			j = arr[i] - 1
			inds = [i, j]
			ln = 2
			while j != i:
				cnt += 1
				done[j] = True
				if abs(j - arr[j] + 1) == 1:
					adj = True
				j = arr[j] - 1
				inds.append(j)
				ln += 1
			inds.sort()
			for j in range(ln - 1):
				if abs(inds[j] - inds[j + 1]) == 1:
					adj = True
	if adj:
		print(cnt - 1)
	else:
		print(cnt + 1)