#H1016. 芙宁娜的帽子戏法

芙宁娜的帽子戏法

题目背景

虽已不再“饰演神明”,但枫丹廷中仍有许多人奉芙宁娜为偶像,而她热爱喧嚣的性格也一时难移。丰沛的情感,热闹的故事,仍如往常一样开演。

题目描述

nn张卡片整齐排列在桌面上,第ii张卡片上写的数字是aia_i。芙宁娜挥动礼帽,滑过卡片的瞬间,桌面上重复的卡片消失了,并且剩下的卡片从小到大排好序,再次划过的瞬间,所有不满足ai=ia_i=i的卡片也消失了。

现在,给出nn张卡片的顺序,以及每张卡片上写的数字{a1,a2,a3,,an}\{a_1,a_2,a_3,\dots,a_n\},请你编程求出经过芙宁娜的帽子戏法后,桌面上的卡片消失了多少张?

例如,n=5{a1,a2,a3,a4,a5}={6,1,2,1,3}n=5,\{a_1,a_2,a_3,a_4,a_5\}=\{6,1,2,1,3\},第22张和第44张卡片重复了,因此会消失一张,剩下的卡片会从小到大排序变成{1,2,3,6}\{1,2,3,6\},因为a4=64a_4=6\neq4,因此写着数字66的卡片也消失了,所以,一共消失了2张卡片。

例如,n=8{a1,a2,a3,a4,a5,a6,a7,a8}={2,3,4,4,5,5,8,4}n=8,\{a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8\}=\{2,3,4,4,5,5,8,4\},第33张卡片、第44张以及第88张卡片重复了,因此会消失22张;第55张卡片和第66张卡片重复了,因此会消失11张;剩下的卡片会从小到大排序变成{2,3,4,5,8}\{2,3,4,5,8\},因为a1=21,a2=32,a3=43,a4=54,a5=85a_1=2\neq1,a_2=3\neq2,a_3=4\neq3,a_4=5\neq4,a_5=8\neq5,所以5张卡片均会消失,因此一共消失了88张卡片,也就是桌面上没有卡片了。

输入输出格式

输入格式

输入共22行。

11行包括一个正整数nn,表示桌面上的卡片数。

22行包括nn个正整数a1,a2,,ana_1,a_2,\dots,a_n,其中aia_i表示第ii张卡片上的数字。

输出格式

一行,共11个整数,代表经过芙宁娜帽子戏法后,桌面上消失的卡片总数。

样例

10
8 7 6 2 10 2 4 1 7 8
8
5
5 2 1 3 4
0
1
1
0

数据范围

  • 对于其中20分的数据满足:n=1n=1
  • 对于另外20分的数据满足:1n1000001\le n \le 1000001,2,3,4,,n1,n1,2,3,4,\dots,n-1,n11~nn每个数至少出现一次。
  • 对于另外20分的数据满足:1n1000,1ai10001\le n \le 1000,1\le a_i \le 1000
  • 对于剩下40分的数据满足:1n100000,1ai1000001\le n \le 100000,1\le a_i \le 100000