There are n boxes. They are numbered with positive integers from 1 to n without repetitions. Additionally, an integer between 1 and n is written on the bottom of each box. Note that there can be several boxes with the same number written on them.

Let us define a move as the following sequence of actions:

1. Choose any box and mark it as current.
2. Remember the number written on the bottom and remove the box.
3. If there exists a box with the number just have been remembered, mark that box as current and go to step 2. Otherwise, the move is over.

Given the numbers written on the bottoms of the boxes you should determine what minimum and maximum number of moves one could possibly make to remove all the boxes.

Input

First line contains an integer n (1 ≤ n ≤ 105). Each of the following n lines contains one number. The i-th of these lines contains the number written on the bottom of the i-th box.

Output

Print two integers: the minimum and maximum number of moves.