在学校艺术节的现场,装饰大厅里排列着 N 盏彩灯,这些彩灯依次悬挂,每盏彩灯上都印有一个正整数,分别记为 A_1, A_2, \dots, A_n。
为了营造出一种独特的视觉效果,策展老师希望对彩灯进行调整:通过熄灭部分彩灯(最多熄灭 N-1 盏),使得剩下仍然亮着的彩灯从左至右显示的数字正好依次为 1, 2, 3, \dots(即第一盏亮灯的数字为 1,第二盏为 2,……,第 i 盏为 i)。
你的任务是帮助策展老师计算,为实现这一目标,最少需要熄灭多少盏彩灯。若无论怎样熄灭,都无法使剩余亮着的彩灯满足要求,则输出 -1。
第一行包含一个整数 N ,表示彩灯的总数。
第二行包含 N 个整数 A_1, A_2, \dots, A_n,表示从左到右每盏彩灯上印的数字。
输出一个整数,表示为了使剩下亮着的彩灯依次显示 1, 2, \dots, i 所需熄灭的最少彩灯数;若无法达到要求,则输出 -1。
5 4 1 3 2 5
3
5 3 4 5 6 2
-1
10 1 6 1 7 2 8 3 4 5 10
5
初始状态下,5 盏灯上的数字分别为:4 1 3 2 5。
只需要熄灭第 1 盏灯、第 3 盏灯、第 5 盏灯,剩余的 2 盏灯上的数字恰好是 1 2,符合题目的要求。
对于 10\% 的数据,满足 A_i \gt 1。
对于 20\% 的数据,满足 1 \le N \le 10。
对于 100\% 的数据,满足 1 \leq N \leq 2 \times 10^5,1 \leq A_i \leq N。