82695 - 换座位
时间限制 : 1 秒
内存限制 : 128 MB
树王国在筹备着举办一次盛大的庆典!
Shirost 作为树王国的庆典设计师,准备邀请 n 个嘉宾来参加本次庆典。庆典上一共准备了 2n 个座位,一个座位最多只能坐一个人且一个人恰好坐一个座位。Shirost 初步计划将第 i 个嘉宾安排在第 i 个座位上。但是总统调查了这 n 个嘉宾的意愿,第 i 个嘉宾的心仪座位为第 a_i 个座位。但除非能坐到心仪座位上,否则他们只愿意坐在原来的座位上。总统希望 Shirost 能够修改计划,使得尽可能多的嘉宾坐在他们的心仪座位上。
形式化的讲,你需要找到长为 n 的数组 b_i (1 \leq i \leq n, 1 \leq b_i \leq 2n) 满足 \forall i \neq j,b_i \neq b_j 且 \forall i, b_i=i 或 b_i=a_i。且最大化 b_i = a_i 的个数。
你只需要输出最多的个数即可。
输入
输入第一行为一个整数 n (1 \leq n \leq 10^{5}),表示总人数。
第二行 n 个整数 a_i (1 \leq a_i \leq 2n),由空格隔开,表示每个人的心仪座位。
输出
输出仅一行一个整数,表示最多有多少嘉宾坐在他们的心仪座位上。
样例
输入
5 2 6 4 5 3
输出
5
提示
对于第一个样例,所有人都可以换到自己的心仪座位。
来源
SNCPC