Minimum Operations to Convert Array

You are given a permutation of 1..n. Operation 1 rotates the array left by one position, and operation 2 swaps any two elements; once operation 2 has been performed, operation 1 can no longer be used. Find the minimum number of operations to turn the array into [1,2,...,n].

输入格式

The first line contains n, and the second line contains n integers arr[i] forming the permutation. This site's judging constraints: 1 ≤ n ≤ 3000; arr is a permutation of 1..n. This range is the runtime bound this site set for the O(n²) reference algorithm.

输出格式

Output a single integer, the minimum number of operations.

样例 1

输入：

5
5 3 2 1 4

输出：

2

样例说明

Enumerate k left rotations. The mapping from positions after rotation to target positions forms a permutation; if it has c cycles, the minimum number of arbitrary swaps is n-c. So the total number of operations is k+n-c; take the minimum over all k.