A permutation of length n is an integer sequence such that each integer from 0 to (n - 1) appears exactly once in it. For example, sequence [0, 2, 1] is a permutation of length 3 while both [0, 2, 2] and [1, 2, 3] are not.

A fixed point of a function is a point that is mapped to itself by the function. A permutation can be regarded as a bijective function. We'll get a definition of a fixed point in a permutation. An integer i is a fixed point of permutation a_0, a_1, ..., a_{n} - 1 if and only if a_{i} = i. For example, permutation [0, 2, 1] has 1 fixed point and permutation [0, 1, 2] has 3 fixed points.

You are given permutation a. You are allowed to swap two elements of the permutation at most once. Your task is to maximize the number of fixed points in the resulting permutation. Note that you are allowed to make at most one swap operation.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^5). The second line contains n integers a_0, a_1, ..., a_{n} - 1 — the given permutation.


-----Output-----

Print a single integer — the maximum possible number of fixed points in the permutation after at most one swap operation.


-----Examples-----
Input
5
0 1 3 4 2

Output
3

Difficulty: interview

Starter code:

Solutions:
n = int(input())
A = list(map(int, input().split()))

cnt = 0
for i in range(n):
	cnt += (A[i] == i)

if cnt == n:
	print(n)
else:
	ind = False
	for i in range(n):
		ind |= (A[i] != i and A[A[i]] == i)
	if ind:
	    print(cnt + 2)
	else:
		print(cnt + 1)

n = int(input())
mass = list(map(int, input().split()))
num = 0
flag = True
for i in range(n):
    if mass[i] == i:
        num += 1
    elif flag and mass[mass[i]] == i:
        num += 2
        flag = False
if flag and num != n:
    num += 1
print(num)

n=int(input())

A=list(map(int,input().split()))
ans=0

E={}
for i in range(n):
    if(A[i]==i):
        ans+=1
    else:
        E[i]=A[i]
done=False
for item in E:
    if(E[E[item]]==item):
        ans+=2
        done=True
        break
if(not done and len(E)>0):
    ans+=1
print(ans)


import sys


n = int(input())
a = list(map(int, input().split()))
ans = 0
par = True
for i in range(n):
    if i == a[i]:
        ans += 1
for i in range(n):
    if i != a[i] and i == a[a[i]]:
        ans += 2
        par = False
        break
if n != 1 and ans < n and par:
    ans += 1
print(ans)

n = int(input())
a = list(map(int, input().split()))
c = 0
t = False
for i in range(len(a)):
    if a[i] == i:
        c += 1
    else:
        if a[a[i]] == i and t == False:
            t = True
if n == c or n - 1 == c:
    print(c)
    return
if t == True:
    print(c + 2)
else:
    print(c + 1)


n, seq = int(input()), list(map(int, input().split()))
counter = found = 0
for i in range(n):
    if seq[i] == i:
        counter += 1
    else:
        found += (seq[seq[i]] == i)
print(counter + 2 * (found > 0) + (counter < n and not found))


n = int(input())
A = list(map(int, input().split()))
count = 0
p = True
for i in range(n):
    if A[i] == i:
        count += 1
    elif p and A[A[i]] == i:
        count += 2
        p = False
if p and count < n -1:
    count += 1
print(count)


def __starting_point():
    inp = input()
    inp = input()
    arr = inp.split()
    ans = 0
    ext = 0
    for i in range(len(arr)):
        if i == int(arr[i]):
            ans += 1
        
        elif int(arr[int(arr[i])])==i:
##            print("Matches")
##            print(i,end=':')
##            print(arr[int(arr[i])])
            ext = max(ext,2)
        else:
##            print(i,end=':')
##            print(arr[int(arr[i])])
            ext = max(ext,1)
##    print(ans)
    ans+=ext
    print(ans)
            

__starting_point()

n = int(input())
data = list(map(int, input().split()))
places = dict()
i = 0
count = 0
check = True
for num in data:
    if num == i:
        count += 1
    elif check:
        if num in places:
            if places[num] == i:
                count += 2
                check = False
            else:
                places[i] = num
        else:
            places[i] = num
    i += 1
if check and count + 1 <= n:
    print(count + 1)
else:
    print(count)

n = int(input())
list1 = list(map(int, input().split()))
replacee = [-1] * n
cnt = 0
swap = False
for i in range(n):
    if list1[i] == i:
        cnt += 1
    else:
        replacee[i] = list1[i]
for i in range(n):
    if replacee[replacee[i]] == i and not swap:
        swap = True
        cnt += 2
if swap:
    print(cnt)
elif replacee != [-1] * n:
    print(cnt + 1)
else:
    print(cnt)


#FixedPoints

numbers = int(input())
array = input().split(" ")
array = [int(x) for x in array]

points = 0
one = False
two = False
for i in range(numbers):
	if array[i] == i:
		points += 1
	else:
		j = array[i]
		if two == False:
			if array[i] == j and array[j] == i:
				two = True
		if one == False:
			if array[i] == j or array[j] == i:
				one = True
if two == True:
	points += 2
elif one == True:
	points += 1
print(points)

n = int(input())
a = list(map(int, input().split()))

res = 0

for i in range(n):
    if a[i] == i:
        res += 1

for i in range(n):
    if a[i] != i and a[a[i]] == i:
        res += 2
        print(res)
        return

if res != n:
    res += 1

print(res)

n = int(input())
a = list(map(int, input().split()))
ans = 0
k = 0
for i in range(n):
    if i == a[i]:
        ans += 1
    elif a[a[i]] == i and k != 2:
        ans += 2
        if k == 1:
            ans -= 1
        k = 2
    elif k == 0:
        ans += 1
        k = 1
print(ans)

n = int(input())
A = list(map(int, input().split()))
C = []
T = False
i = 0
k = 0
while i < n:
    if A[i] != i:
        a = (max(A[i], i), min(A[i], i))
        C.append(a)
    else:
        k += 1
    i += 1
C.sort()
for i in range(len(C) - 1):
    if C[i] == C[i + 1]:
        T = True
        break
if n == k:
    print(k)
elif T:
    print(k + 2)
else:
    print(k + 1)


n = int(input())
a = list(map(int, input().split()))
fixed = extra = 0
for i in range(n):
    if a[i] == i:
        fixed += 1
    elif a[a[i]] == i:
        extra = 2
    elif not extra:
        extra = 1
print(fixed + extra)


n = int(input())
a = list(map(int, input().split()))
ans = 0
b = True
for i in range(n):
    if a[i] == i:
        ans += 1
    elif a[a[i]] == i and b:
        ans += 2
        b = False
if b and ans < n:
    ans += 1
print(ans)

N=int(input())
i=0
j=0
num=[]
new=[]
k=0
total=0
isSorted=False
flagDouble=False
IN=input().split()
while(i<N):
		k=int(IN[i])
		num.append((k,i))
		new.append(k)
		if i==new[i]:
				total=total+1
		i=i+1
if total==N:
		isSorted=True
else:
		num.sort()
# for i in range(N):
# 		j=num[i][1]
# 		if j==new[j] and i!=j:
# 				flagDouble=True
# 				break

for i in range(N):
		j=num[i][1]
		if i==new[j] and j==new[i] and i!=j:
				flagDouble=True

# print(total)
# print(num)
# print(new)
# print(isSorted)
# print(flagDouble)
if flagDouble:
		print(total+2)
elif not isSorted:
		print(total+1)
else:
		print(total)


n = int(input())
a = list(map(int, input().split()))
b = 0
c = 0
for i, j in enumerate(a):
  if i == j:
    b += 1
  elif a[j] == i:
    c = 2
  elif c == 0:
    c = 1
print(b + c)


3

n = int(input())
lst = list(map(int, input().split()))
good = len([i for i in range(n) if lst[i] == i])
best = len([i for i in range(n) if i != lst[i] and lst[lst[i]] == i])
var = len([i for i in range(n) if i != lst[i] and lst[lst[i]] != lst[i]])
print(good + (2 if best else (var > 0)))


n = int(input())
arr = [int(x) for x in input().split(' ')]
paired, fixpoints = 0, 0
for x in range(n):
    if arr[x] == x: fixpoints += 1
    else:
        if arr[arr[x]] == x: paired += 1
if fixpoints == n:
    print(fixpoints)
elif paired > 0:
    print(fixpoints+2)
else:
    print(fixpoints+1)


def main():
        n = int(input())
        v = list(map(int,input().split()))
        a,c1,ok = 0,0,0
        for i in range(n):
                if (v[i] == i):
                        c1 = c1 + 1
                elif (v[v[i]] == i):
                        ok = 1
        if (c1 == n):
                print(c1)
        elif (ok):
                print(c1+2)
        else:
                print(c1+1)
    

def __starting_point():
    main()



__starting_point()

n=int(input())
a=list(map(int,input().split()))
done=True
ans=0
for i in range(n) :
    if a[i]==i:
        ans+=1
       
    elif done:
        if a[a[i]]==i:
            ans+=2
            done=False

if done and(ans<len(a)-1):ans+=1
print(ans)
    


n = int(input())
a = list(map(int, input().split()))
c = 0
for i in range(n):
  if a[i] == i:
    c += 1
if c < n:
  for i in range(n):
    if a[i] != i and a[a[i]] == i:
      c += 2
      break
  else:
    c += 1
print(c)

input()
a = [int(x) for x in input().split()]

count = 0
m = {}
yes = False
for i, b in enumerate(a):
    if b == i:
        count += 1
    elif not yes:
        if b in m and i == m[b]:
            yes = True
        else:
            m[i] = b
count += 2 if yes else 1 if len(m) else 0
print("%d" % count)


n = int(input())
a = [int(x) for x in input().split()]
ans = 0
flag = True
for i in range(n):
    if a[i] == i:
        ans += 1
    elif a[a[i]] == i and flag:
        ans += 2
        flag = False
if flag and ans < n:
    ans += 1
print(ans)