- Time limit: 2.00 s
- Memory limit: 256 MB
Teemu is an assistant at the course CS-A1150 - Databases. One of the tasks on the course is to create a family database.
A family database consists of n entries numbered 1, 2, 3, \ldots n each representing a family member. Each entry i has a single number p_i pointing to the parent of the entry.
As we all know nobody can be their own ancestor. Still many of the students have managed to create databases with cycles. A cycle is a set of k nodes \{a_1, a_2, \dotsc, a_k\} for some k\ge 2 such that a_{i+1} is the parent of a_i for all i = 1, 2, \dotsc, k-1 and finally a_1 is the parent of a_k.
As the assistant of the course, Teemu needs your help to count cycles in the students' databases.
Input
The first line contains a single integer, n, the number of entries in the database.
The second line contains n integers, p_1, p_2, \ldots, p_n. We have 1 \le p_i \le n and p_i \ne i for all i.
Output
Output a single integer, the number of cycles in the given database.
Limits
- 2 \le n \le 10^6
Example 1
Input:
16 2 3 4 5 6 1 4 7 7 4 12 11 14 15 13 13
Output:
3
Explanation: Cycles in the input are \{1, 2, 3, 4, 5, 6\}, \{11, 12\} and \{13, 14, 15\}.