[POI2008]枪战Maf

有 $n$ 个人，编号为 $1$ 到 $n$。每个人手中都有一把手枪，并在开始时选定一个人作为瞄准目标，也可以瞄准自己。

选定这 $n$ 个人的一个排列，并按照排列顺序依次让他们行动。轮到某个人时，如果他此前已经死亡，则不能开枪；否则，他会向最初瞄准的人开枪，使目标死亡，目标也可能是他自己。

每个人至多开枪一次，且任意时刻只有一个人开枪。不同的排列可能产生不同的死亡人数。求最终死亡人数的最小值和最大值。

输入格式

第一行包含一个整数 $n$，表示人数。

第二行包含 $n$ 个整数 $\mathit{aim}_1,\mathit{aim}_2,\ldots,\mathit{aim}_n$，其中 $\mathit{aim}_i$ 表示第 $i$ 个人瞄准的人。

输出格式

输出两个整数，分别表示最终死亡人数的最小值和最大值。

样例输入

8
2 3 2 2 6 7 8 5

样例输出

3 5

数据范围

• $1\le n\le 10^6$；
• $1\le \mathit{aim}_i\le n$。

来源与许可

本题为 POI 2008 试题「枪战 Maf」，题面与测试数据整理自 BZOJ。

样例 1

输入

8
2 3 2 2 6 7 8 5

输出

3 5