cho.sh

Minimum Difference to a Perfect Permutation

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'.

Medium6MathGraphGreedyImplementationNo attempts yetTime limit2sMemory limit128 MB

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.

  1. B[0] = 0
  2. 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.

AB
0, 1, 20, 0, 0
0, 2, 10, 0, 0
1, 0, 20, 1, 0
1, 2, 00, 1, 2
2, 0, 10, 2, 1
2, 1, 00, 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.