[GDKOI2024 普及组] 读书

赛事要求

2024 年广东省重点中学信息学邀请赛 (GDKOI 2024)

普及组 第二试

2024 年 1 月 7 日

注意事项

1. 严格按照题目所要求的格式进行输入、输出，否则严重影响得分。
2. 题目测试数据有严格的时间限制，超时不得分。
3. C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须是 0。
4. 输入文件格式不用判错；输入输出文件名均已给定，不用键盘输入。
5. 评测环境为 NOI 系列活动标准竞赛环境，编译器版本为 g++ 9.4.0。
6. 若无特殊说明，结果的比较方式为全文比较 (过滤行末空格及文末回车)。
7. 对于 C++ 选手，64 位整数输入输出格式为 %lld。
8. 选手提交的程序源文件必须不大于 100KB。
9. 对于 C++ 语言的编译选项为 -O2 -std=c++14

题目描述

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

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

每天，Zayin 都会从头到尾开始阅读这本书。对于她还不能读懂的章节（由于限制）或是已经阅读过的章节，Zayin 会在那天跳过它们。

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

输入格式

第一行包含两个整数 $d, n$，表示测试点编号和章节数。

第二行包含 $n$ 个整数 $a_i (0 \leq a_i < n)$，表示限制。

输出格式

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

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

样例 #1

样例输入 #1

1 10
3 4 0 6 1 1 0 8 6 3

样例输出 #1

2

提示

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

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

• Subtask 1（10%）：$1 ≤ n ≤ 10$，$d = 1$。
• Subtask 2（10%）：$1 ≤ n ≤ 500$，$d = 2$。
• Subtask 3（20%）：$1 ≤ n ≤ 5000$，$3 \leq d \leq 4$。
• Subtask 4（20%）：$1 ≤ n ≤ 10^5$，$5 \leq d \leq 6$。
• Subtask 5（40%）：$1 ≤ n ≤ 5 \times 10^5$，$7 \leq d \leq 10$。