Mob Feud

Mob feud rages in Equatorial Byteotia. The mob bosses have come to Byteburg, the country’s capital, to settle their disputes. During tense negotiations, each mobster draws his pistol and aims at another. They will shoot one by one according to a certain order obeying the following code of honour:

• The participants shoot in a specific order and at any moment at most one of them is shooting.
• No shooter misses his target; his target dies instantly and will not get a chance to shoot if shot before his turn.
• Every mobster is scheduled to shoot once, provided he has not been shot before his turn arrives.
• No participant may change his initial target even if the target is already dead (in which case the shot causes no further damage).

An undertaker, watching from afar, counts a profit in the ensuing mayhem. However, he wishes to know the tightest possible range for the number of casualties – both the minimum and maximum that could result – given that he knows who aims at whom but not the shooting order.

Your task is to determine these two numbers.

Explanation:

The shooting scenario can be represented as a directed graph with n nodes (mobsters) where each node has an outgoing edge (its chosen target). Every connected component of this graph contains exactly one cycle. For cycles of length at least 3, it is possible to order the shooters so that every mobster in the cycle survives long enough to shoot, resulting in all n casualties for that component. However, in a 2‐cycle (i.e. two mobsters aiming at each other), no matter what order is chosen, only one mobster gets to shoot before being killed, which reduces the maximum casualty count by 1 for each 2‐cycle.

Thus, if ∙ Let n be the total number of mobsters,
∙ Let c be the number of cycles in the graph,
∙ Let t be the number of 2‐cycles,

Then the minimum casualties equals c (each cycle contributes at least one casualty) and the maximum casualties equals n − t.

Formally, using LaTeX for formulas, the answers are given by:

\( \text{min casualties} = c \)

\( \text{max casualties} = n - t \)

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), the number of mobsters. The second line contains n space-separated integers. The i-th integer (1-indexed) denotes the target of the i-th mobster. It is guaranteed that no mobster targets himself, i.e. for every i, the i-th integer is not i.

outputFormat

Output two space-separated integers: the minimum and maximum number of casualties possible.

sample

2
2 1

1 1

</p>