ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ufa SATU contest. Petrozavodsk training camp. Summer 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

A. Team building

Time limit: 1.0 second
Memory limit: 64 MB
There are n programmers in the software development company. Each of them thinks that he is the greatest or the second greatest programmer in the company. In the latter case he can name the greatest programmer in his opinion.
The administration decided to divide all programmers into development teams using the following algorithm:
  1. If there are programmers, who are not assigned to a development team, choose any of them and mark him as current one.
  2. Create a new development team and assign it to the current programmer.
  3. If the current programmer thinks that one of his colleagues is the greatest programmer and this colleague is not assigned to a development team, then this colleague is assigned to the same development team and is marked as current programmer. Then the step 3 is repeated. Otherwise, the team is formed, and the administration returns to the step 1.
What is the minimal and maximal number of teams which can be formed in this company according to the algorithm?


The first line contains an integer n (1 ≤ n ≤ 105). The i-th of the following n lines contains the number of the programmer, who is the greatest, according to the i-th programmer's opinion.


Output the minimal and maximal number of development teams, separated with space.


1 2
Problem Author: Artyom Ripatti
Problem Source: Ufa SATU Contest. Petrozavodsk Summer Session, August 2009
To submit the solution for this problem go to the Problem set: 1742. Team building