体育老师拿出nn个气球从左到右排成一排,每个气球上面都会有一个数字编号a i
你可以选择扎破某一些气球,但是最多只能扎破n-1n−1个气球,至少要剩下一个气球留在场上。
假设目前你已经扎破了一些气球,场上还剩下mm个气球,那么胜利的规则是这mm个气球中的每一个气球i(1 \leq i \leq m)i(1≤i≤m),如果气球上的数 i 恰好等于ii,那么你将赢得游戏的胜利!
由于你的体力有限,所以你需要找到最小的扎破气球的数目,使得你能获得游戏的胜利,并把这个最小的数目输出出来;而如果无论怎么扎破气球都没办法赢得胜利,那么输出-1.
输入格式
第一行输入一个整数nn表示气球的数量;
第二行输入nn个整数a 1a 2...... a n,表示第ii个气球上写着的数字。
输出
输出能赢得游戏胜利的,最小的扎破气球的个数。 如果不能赢得游戏,输出 -1。
输入数据 1
3
2 1 2
输出数据 1
1
输入数据 2
3
2 2 2
输出数据 2
-1
输入数据 3
10
3 1 4 1 5 9 2 6 5 3
输出数据 3
7
输入数据 4
1
1
输出数据 4
0
样例说明
样例1:把第一个气球扎破之后,剩下气球的数字序列是1、21、2,恰好使得第11个气球数字是11,第二个气球数字是22。
样例2:无论扎破哪些气球,都不能满足胜利条件。