P3472 [POI 2008] MAF-Mafia

在赤道 Byteotia，黑帮之间的争斗愈演愈烈。黑帮老大们来到该国的首都 Byteburg，以解决争端。 谈判非常紧张，在某个时刻，手痒的参与者们拔出了他们的枪。 每个参与者都用手枪瞄准另一个人。 如果他们开始大开杀戒，射击将按照以下荣誉代码进行： 参与者按一定顺序射击，并且在任何时刻最多只有一个人开枪，射手不会失手，他的目标会立即死亡，因此他之后不能再开枪，每个人都开一次枪，前提是他在有机会开枪之前没有被击中，任何参与者都不能改变他最初选择的目标，即使目标已经死了（那么射击不会造成进一步的伤亡）。 一个殡葬承办人从远处观察，正如他通常所做的那样。毕竟，黑帮分子从未让他的生意冷清过。 他在射击中看到了潜在的利润，但他想知道准确的估计。他想知道最小和最大可能的死亡率。 殡葬承办人看到谁瞄准了谁，但不知道射击的顺序。 你需要编写一个程序来确定他如此渴望知道的数字。 任务 编写一个程序： 从标准输入读取每个黑帮分子选择的目标，确定最小和最大伤亡人数，将结果写入标准输出。

标准输入的第一行包含参与者的数量 $n$ ($1 \le n \le 1{,}000{,}000$)。 他们的编号从 $1$ 到 $n$。 第二行包含 $n$ 个整数 $s_1,s_2,\cdots,s_n$，用单个空格分隔，$1 \le s_i \le n$。 $s_i$ 表示第 $i$ 个参与者的目标编号。 注意，可能存在 $s_i=i$ 的情况（紧张导致的）。

你的程序应在标准输出的第一行输出两个用单个空格分隔的整数。这些数字分别是射击导致的最小和最大伤亡人数。

题面翻译由 ChatGPT-4o 提供。