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

1742. 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?

Input

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

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

Sample

inputoutput
4
2
3
4
2
1 2
Problem Author: Artyom Ripatti
Problem Source: Ufa SATU Contest. Petrozavodsk Summer Session, August 2009