Given any permutation of the numbers {0, 1, 2,..., N-1}, it is easy to sort them in increasing order. But what if Swap(0, *) is the ONLY operation that is allowed to use? For example, to sort {4, 0, 2, 1, 3} we may apply the swap operations in the following way:

Swap(0, 1) => {4, 1, 2, 0, 3}
Swap(0, 3) => {4, 1, 2, 3, 0}
Swap(0, 4) => {0, 1, 2, 3, 4}

Now you are asked to find the minimum number of swaps need to sort the given permutation of the first N nonnegative integers.

Input Specification:

Each input file contains one test case, which gives a positive N (<=10⁵) followed by a permutation sequence of {0, 1, ..., N-1}. All the numbers in a line are separated by a space.

Output Specification:

For each case, simply print in a line the minimum number of swaps need to sort the given permutation.

Sample Input:

10 3 5 7 2 6 4 9 0 8 1

Sample Output:

9

 #include<cstdio>

 #include<stack>

 #include<cstring>

 #include<iostream>

 #include<stack>

 #include<set>

 #include<map>

 using namespace std;

 map<int,int> ha;

 bool vis[];

 void DFS(int cur,int s){

     vis[cur]=true;

     if(ha[cur]==s){

         return;

     }

     DFS(ha[cur],s);

 }

 //统计点的数量>1的环的个数，有0在的换交换次数是个数-1；没有0在的环，交换次数是个数+1

 int main(){

     //freopen("D:\\INPUT.txt","r",stdin);

     int count,n;

     scanf("%d",&n);

     count=n;

     int i,num;

     for(i=;i<n;i++){

         scanf("%d",&num);

         if(num==i){//去掉元素个数为0的环，剩下的元素个数

             vis[num]=true;

             count--;

         }

         ha[num]=i;

     }

     //剩下的环除了包含元素0的环，其他环的交换次数=环自身元素个数+1

     for(i=;i<n;i++){

         if(!vis[i]){

             DFS(i,i);

             count++;

         }

     }

     if(ha[]!=){//如果0不单独成环，说明有元素个数>1的环包含0，则这个环在34行时多加了2，这里减去

         count-=;

     }

     printf("%d\n",count);

     return ;

 }