Brick Break

题目描述

我们有 $N$ 块砖按照从左到右的一排排列。
从左数第 $i$ 块砖 $(1 \leq i \leq N)$ 上写着一个整数 $a_i$。
在它们之中，你最多可以选择打碎 $N-1$ 块砖。
假设剩下了 $K$ 块砖。若对于每个整数 $i$ $(1 \leq i \leq K)$，从左数第 $i$ 块剩下的砖上写着整数 $i$，则 Snuke 会满足。
求使 Snuke 满意所需打碎的最少砖块数。如果无法满足他的愿望，则输出 $-1$。

输入格式

输入由标准输入提供，格式如下：
$N$
$a_1$ $a_2$ $...$ $a_N$

输出格式

输出使 Snuke 满意所需打碎的最少砖块数；如果无法满足他的愿望，则输出 $-1$。

3
2 1 2

1

3
2 2 2

-1

10
3 1 4 1 5 9 2 6 5 3

7

1
1

0

提示

输入中的所有数值均为整数。
$1 \leq N \leq 200000$
$1 \leq a_i \leq N$如果我们打碎最左边的砖，剩下的砖从左到右分别写着整数 $1$ 和 $2$，在这种情况下 Snuke 会满足。
在这种情况下，没有办法通过打碎某些砖来满足 Snuke 的愿望。
也可能根本不需要打碎任何砖。

标签: AtCoder|abc148D

来源

AtCoder|abc148D