题目描述

题目译自 XV OI Olimpiada Informatyczna – II etap Mafia

有 $n$ 位黑帮首领，每位首领 $i$ 瞄准固定目标 $s_i$（可瞄准自己）。枪战规则如下：

1. 首领按某一顺序依次开枪，每次仅一人射击；
2. 射击必中，被击中者立即死亡，无法再开枪；
3. 每人仅射击一次（若未提前死亡）；
4. 即使目标已死，仍需射击（但不增加受害人数）。

需计算可能的最小受害人数和最大受害人数（受害人数指枪战中被击毙的首领数量）。

输入格式

1. 第一行：整数 $n$（$1 \leq n \leq 10^6$，首领人数，编号 1~n）；
2. 第二行：$n$ 个整数 $s_1, s_2, \dots, s_n$（$1 \leq s_i \leq n$，首领 $i$ 的瞄准目标）。

输出格式

输出一行，包含两个整数，分别表示最小受害人数和最大受害人数。

样例

输入

8
2 3 2 2 6 7 8 5

输出

3 5