题目描述

Zayin 是一个热爱读书的学生。

最近，Zayin 收到了一本有 $n$ 个章节的书，其中每个章节 $i$ 都有一个限制：她必须至少阅读了其他 $a_i$ 个章节，才能够获取足够的智慧来读懂该章节。

每天，Zayin 都会从头到尾开始阅读这本书。对于她还不能读懂的章节（由于限制）或是已经阅读过的章节，Zayin 会在那天跳过它们。如果在当天从头到尾阅读的过程中，前面刚读过的章节使后面章节满足了限制，她也可以紧接着阅读后面的章节。

现在，Zayin 想要知道至少需要多少天才能阅读完所有的 $n$ 个章节。

输入格式

第一行包含一个整数 $n$，表示书的章节数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每个章节的限制。

输出格式

输出一行包含一个整数，表示最少需要的天数。

如果 Zayin 无法阅读完所有的 $n$ 个章节，输出 $-1$。

样例

10
3 4 0 6 1 1 0 8 6 3

2

样例解释

第一天从头到尾阅读：

• 章节 $1$（$a_1=3$）：已读章节数为 $0$，不足 $3$，跳过；
• 章节 $2$（$a_2=4$）：已读章节数为 $0$，不足 $4$，跳过；
• 章节 $3$（$a_3=0$）：已读章节数为 $0$，满足，阅读。已读章节数变为 $1$；
• 章节 $4$（$a_4=6$）：已读章节数为 $1$，不足 $6$，跳过；
• 章节 $5$（$a_5=1$）：已读章节数为 $1$，满足，阅读。已读章节数变为 $2$；
• 章节 $6$（$a_6=1$）：已读章节数为 $2$，满足，阅读。已读章节数变为 $3$；
• 章节 $7$（$a_7=0$）：满足，阅读。已读章节数变为 $4$；
• 章节 $8$（$a_8=8$）：已读章节数为 $4$，不足 $8$，跳过；
• 章节 $9$（$a_9=6$）：已读章节数为 $4$，不足 $6$，跳过；
• 章节 $10$（$a_{10}=3$）：已读章节数为 $4$，满足，阅读。已读章节数变为 $5$。

第一天结束后，已读章节为 $\{3,5,6,7,10\}$。

第二天从头到尾阅读：

• 章节 $1$（$a_1=3$）：已读章节数为 $5$，满足，阅读；
• 章节 $2$（$a_2=4$）：已读章节数为 $6$，满足，阅读；
• 章节 $3$：已读，跳过；
• 章节 $4$（$a_4=6$）：已读章节数为 $7$，满足，阅读；
• 章节 $5$：已读，跳过；
• 章节 $6$：已读，跳过；
• 章节 $7$：已读，跳过；
• 章节 $8$（$a_8=8$）：已读章节数为 $8$，满足，阅读；
• 章节 $9$（$a_9=6$）：已读章节数为 $9$，满足，阅读；
• 章节 $10$：已读，跳过。

第二天结束后，所有章节阅读完毕。因此最少需要 $2$ 天。

数据范围与提示

本题使用子任务捆绑测试。

对于所有测试数据，保证 $1 \leq n \leq 5 \times 10^5$，$0 \leq a_i < n$。

• Subtask 1（10%）：$1 \le n \le 10$。
• Subtask 2（10%）：$1 \le n \le 500$。
• Subtask 3（20%）：$1 \le n \le 5000$。
• Subtask 4（20%）：$1 \le n \le 10^5$。
• Subtask 5（40%）：$1 \le n \le 5 \times 10^5$。