Minimum Difference to a Perfect Permutation

Time limit2sMemory limit128 MB

Summary

Given a permutation, determine the minimum number of positions to change so it becomes a single N-cycle, which is the condition for a 'perfect permutation'.

Level: Medium6 of 10
Topics: Math, Graph, Greedy, Implementation
Solved: No attempts yet

Problem

Let A[0], A[1], ..., A[N-1] be a permutation containing every integer from 0 to N-1 exactly once. From A, define a child array B of the same length as follows.

B[0] = 0
B[i] = A[B[i-1]] (1 <= i <= N-1)

If the child array B produced by this process is also a permutation containing every integer from 0 to N-1 exactly once, then A is called a perfect permutation.

The following table shows every permutation A of length 3 and its child array B. The permutations {1, 2, 0} and {2, 0, 1} are perfect permutations because their child arrays are also permutations.

A	B
0, 1, 2	0, 0, 0
0, 2, 1	0, 0, 0
1, 0, 2	0, 1, 0
1, 2, 0	0, 1, 2
2, 0, 1	0, 2, 1
2, 1, 0	0, 2, 0

You are given a permutation P of length N. Find a perfect permutation Q whose difference from P is as small as possible. The difference between two permutations P and Q is the number of indices i such that P[i] and Q[i] are different.

Input

The first line contains the size N of permutation P (1 <= N <= 50). The second line contains permutation P, which includes every integer from 0 to N-1 exactly once.

Output

Print the minimum possible difference between the given permutation P and a perfect permutation Q.

Examples5

Example 1
Input
```
5
2 0 1 4 3
```
Expected output
```
2
```
Example 2
Input
```
3
2 0 1
```
Expected output
```
0
```
Example 3
Input
```
4
2 3 0 1
```
Expected output
```
2
```
Example 4
Input
```
6
0 5 3 2 1 4
```
Expected output
```
3
```
Example 5
Input
```
10
4 2 6 0 3 5 9 7 8 1
```
Expected output
```
5
```