D - 破坏砖块

分数：$400$ 分

问题描述

我们有 $N$ 个砖块从左到右排列。

从左侧开始，第 $i$ 个砖块 $(1 \leq i \leq N)$ 上写着整数 $a_i$。

其中，你可以最多打碎 $N-1$ 个砖块。

让我们设还剩下 $K$ 个砖块。当满足每一个整数 $i$ $(1 \leq i \leq K)$，最左侧的第 $i$ 个砖块上写着整数 $i$ 的时候，Snuke 就会满意。

找出满足 Snuke 的要求所需最小的砖块打碎数量。如果无法满足他的要求，则输出 -1。

约束

• 所有输入值都是整数。
• $1 \leq N \leq 200000$
• $1 \leq a_i \leq N$

输入

输入以以下格式给出：

$N$

$a_1$ $a_2$ $...$ $a_N$

输出

输出最少需要打碎的砖块数以满足 Snuke 要求，如果无法满足他的要求，则输出 -1。

3
2 1 2

1

如果我们打碎最左侧的砖块，剩下的砖块上写着整数 $1$ 和 $2$，这时 Snuke 就会满意。

3
2 2 2

-1

在这种情况下，无论如何都无法打破一些砖块来满足 Snuke 的要求。

10
3 1 4 1 5 9 2 6 5 3

7

1
1

0

可能根本不需要打破砖块。