AT_abc148_d [ABC148D] Brick Break

题目描述

有 $N$ 块砖头横向排成一列。

从左起第 $i$ 块砖头上写有整数 $a_i$。

你可以选择至多 $N-1$ 块任意的砖头进行敲碎。

结果，假设剩下 $K$ 块砖头。此时，如果对于任意整数 $i\ (1 \leq i \leq K)$，剩下的砖头中从左起第 $i$ 块上写的整数恰好为 $i$，那么“すぬけさん”会感到满意。

请输出为了让“すぬけさん”满意，最少需要敲碎的砖头数。如果无论怎么敲碎都无法满足条件，则输出 $-1$。

输入格式

输入以以下格式从标准输入读入。

$N$ $a_1$ $a_2$ $\ldots$ $a_N$

输出格式

请输出为了让“すぬけさん”满意，最少需要敲碎的砖头数。如果无论如何都无法满足条件，则输出 $-1$。

样例 1

输入

3
2 1 2

输出

1

样例 2

输入

3
2 2 2

输出

-1

样例 3

输入

10
3 1 4 1 5 9 2 6 5 3

输出

7

样例 4

输入

1
1

输出

0

说明/提示

限制条件

• 输入均为整数。
• $1 \leq N \leq 200000$
• $1 \leq a_i \leq N$

样例解释 1

如果敲碎最左边的 $1$ 块砖头，剩下的砖头上写的整数从左到右为 $1$、$2$。此时，“すぬけさん”会感到满意。

样例解释 2

在这种情况下，没有任何一种敲碎砖头的方法能让“すぬけさん”满意。

样例解释 4

有时也可以一块砖头都不敲碎。

由 ChatGPT 4.1 翻译