c++戳气球问题！！

Question

体育老师拿出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：无论扎破哪些气球，都不能满足胜利条件。

Answer 1

oiclass