3865 - 彩灯

题目描述

在学校艺术节的现场,装饰大厅里排列着 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
说明

样例 1 说明

初始状态下,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^51 \leq A_i \leq N

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 入门


上一题 下一题