题目背景
虽已不再“饰演神明”,但枫丹廷中仍有许多人奉芙宁娜为偶像,而她热爱喧嚣的性格也一时难移。丰沛的情感,热闹的故事,仍如往常一样开演。
题目描述
有n张卡片整齐排列在桌面上,第i张卡片上写的数字是ai。芙宁娜挥动礼帽,滑过卡片的瞬间,桌面上重复的卡片消失了,并且剩下的卡片从小到大排好序,再次划过的瞬间,所有不满足ai=i的卡片也消失了。
现在,给出n张卡片的顺序,以及每张卡片上写的数字{a1,a2,a3,…,an},请你编程求出经过芙宁娜的帽子戏法后,桌面上的卡片消失了多少张?
例如,n=5,{a1,a2,a3,a4,a5}={6,1,2,1,3},第2张和第4张卡片重复了,因此会消失一张,剩下的卡片会从小到大排序变成{1,2,3,6},因为a4=6=4,因此写着数字6的卡片也消失了,所以,一共消失了2张卡片。
例如,n=8,{a1,a2,a3,a4,a5,a6,a7,a8}={2,3,4,4,5,5,8,4},第3张卡片、第4张以及第8张卡片重复了,因此会消失2张;第5张卡片和第6张卡片重复了,因此会消失1张;剩下的卡片会从小到大排序变成{2,3,4,5,8},因为a1=2=1,a2=3=2,a3=4=3,a4=5=4,a5=8=5,所以5张卡片均会消失,因此一共消失了8张卡片,也就是桌面上没有卡片了。
输入输出格式
输入格式
输入共2行。
第1行包括一个正整数n,表示桌面上的卡片数。
第2行包括n个正整数a1,a2,…,an,其中ai表示第i张卡片上的数字。
输出格式
一行,共1个整数,代表经过芙宁娜帽子戏法后,桌面上消失的卡片总数。
样例
10
8 7 6 2 10 2 4 1 7 8
8
5
5 2 1 3 4
0
1
1
0
数据范围
- 对于其中20分的数据满足:n=1
- 对于另外20分的数据满足:1≤n≤100000且1,2,3,4,…,n−1,n即1~n每个数至少出现一次。
- 对于另外20分的数据满足:1≤n≤1000,1≤ai≤1000
- 对于剩下40分的数据满足:1≤n≤100000,1≤ai≤100000