Problem C
Job Switching

You and your friends all work at different companies. However, not everyone may be satisfied with their current job. You therefore asked JobAgent to find out if there’s a job that fits you even better. After some computation, JobAgent came back with a list for which job is the best for each of you. The best thing is that each of you is already working at one of these jobs! As the good employees you are, you would never want to leave a job without a replacement, and never be unemployed at any time. The only reasonable solution is thus to repeatedly switch jobs with each other. How many times do two persons have to switch jobs with each other to get everyone to the job that JobAgent suggested?


The first line of the input consists of an integer $N$ ($2 \le N \le 3\cdot 10^5$), the number of friends (including yourself) to switch jobs.

This is followed by a line containing $N$ integers. The $i$’th of these contains the number of the person that currently has the job that the $i$’th person fits best for. Every person is numbered between $1$ and $N$. It is guaranteed that for each job there is exactly one person that fits it best.


Output a single integer, the smallest number of job switches that needs to be performed.

Explanation of sample 2

Nobody has the right job from the beginning. Three switches are sufficient for everyone to get the right job. Initially, the two first peoples can switch jobs, so that everyone has the jobs 3 2 4 1 and person $2$ gets the right job. Then, person $3$ and $4$ can switch jobs, resulting in the jobs 3 2 1 4. Lastly, only person $1$ and $3$ has the wrong jobs, and can switch with each other to finish the process.

Sample Input 1 Sample Output 1
3 2 1
Sample Input 2 Sample Output 2
2 3 4 1
Sample Input 3 Sample Output 3
2 1

Please log in to submit a solution to this problem

Log in