小蓝想要组织一场擂台赛,比赛共有 n 位选手,编号为 1 至 n。初始时,每位选手 i 都在属于自己的第 i 号擂台上。每位选手 i 都有且仅有一个想要前往挑战的目标擂台 ai。
比赛开始时,小蓝需要制定一个出战顺序。按照该顺序,对于每一位出战选手 i:
• 如果他的目标擂台 ai 目前未被关闭,他将离开自己的 i 号擂台并前往 ai
号擂台发起挑战,同时关闭自己原先所在的擂台 i。
• 如果他的目标擂台 ai 已被关闭,则他无法发起挑战,只能留在原地。
小蓝希望设置一个出战顺序,使得最终被使用过(即作为挑战目标被成功前往)的擂台数量尽可能少。需要注意的是,留在原地的选手并不计入对擂台的使用。
请你帮小蓝计算,在最优的出战顺序下,最少有多少个擂台被使用过?
输入共 2 行。
第一行为一个正整数 n,表示选手数量。
第二行为 n 个正整数 a1, a2,. . . , an,表示每位选手的目标擂台编号。
输出一个整数,表示最少被使用过的擂台数量。
5 2 3 4 5 4
2
【样例说明】
其中一种最优的出战顺序为:1, 3, 2, 5, 4。
1. 选手 1 挑战 2:目标擂台 2 未关闭,出战成功,关闭擂台 1,使用擂台2;
2. 选手 3 挑战 4:目标擂台 4 未关闭,出战成功,关闭擂台 3,使用擂台4;
3. 选手 2 挑战 3:目标擂台 3 已被选手 3 出战时关闭,选手 2 只能留在原地;
4. 选手 5 挑战 4:目标擂台 4 未关闭,出战成功,关闭擂台 5,使用擂台4;
5. 选手 4 挑战 5:目标擂台 5 已被选手 5 出战时关闭,选手 4 只能留在原地。
最终被使用过的擂台为 {2, 4},共 2 个。
【评测用例规模与约定】
对于 30% 的数据,n ≤ 10;
对于 100% 的数据,1 ≤ n ≤ 106,1 ≤ ai ≤ n 且 ai != i。