2828. 出题表人

【题目描述】

Hyoi有n 个人，愉♂快地生活在一起。直到有一天他们学会了出题互表。

每个人都有且仅有一个表的目标(这个目标有可能是他自己，这叫自表)。对于那些没人表

的人(其他所有人表的目标都不是他)，他们想刷存在感，于是可以选择放弃表自己的目标而选

择自表(也就是二选一)。

注意只有一开始没有作为任何人的目标的人才可以放弃目标选择自表。

规定轮到某个没有被表的人时，必须且仅能表一次。所有被表过的人都不能再表别人了。

当然一个人可以被表很多次。如某WCG...

由你来决定一个顺序，大家按照顺序行动。求问最后被表的人数的最小值和最大值。

【输入格式】

第一行一个整数n

第二行n 个整数，第i 个整数ai 表示第i 个人的目标，满足1 <= ai <= n

【输出格式】

两个整数，依次表示最小值和最大值

【样例输入】

8



2 3 2 2 6 7 8 5

【样例输出】

3 6

【样例解释】

最小值：按照1,4,2,3,5,6,7,8 的顺序行动。轮到2，6，8 时它们已经被表所以他们不能再

表人。最后被表的人数是3

最大值：1 和4 自表，然后剩下的人按照2,3,7,6,5 的顺序行动。这样一来3，6，7，8 也

会被表。于是一共有6 个人被表

【数据范围】

• 对于前30% 的数据，满足1 <= n <= 8

• 对于接下来30% 的数据，满足只有前若干个人自表，后面的第i 个人只会表1 ... i-1 中

的某一个人

• 对于所有数据，满足1 <= n <= 10e6

【来源】

qbxt 2017.10.3 t3