Problem C
Job Switching
Languages
en
sv
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?
Input
The first line of the input consists of an integer
This is followed by a line containing
Output
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
Sample Input 1 | Sample Output 1 |
---|---|
3 3 2 1 |
1 |
Sample Input 2 | Sample Output 2 |
---|---|
4 2 3 4 1 |
3 |
Sample Input 3 | Sample Output 3 |
---|---|
2 2 1 |
1 |