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:
- If there are programmers, who are not assigned to a development team, choose any of them and mark him as current one.
- Create a new development team and assign it to the current programmer.
- 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.
Problem Author: Artyom Ripatti
Problem Source: Ufa SATU Contest. Petrozavodsk Summer Session, August 2009