4729: 读书(广东省重点中学信息学邀请赛普及组)

内存限制:512 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:2 解决:0

题目描述

(广东省重点中学信息学邀请赛 (GDKOI 2024 day2普及组 第二试)

Zayin是一个热爱读书的学生。
最近,Zayin收到了一本有n个章节的书,其中每个章节i都有一个限制:她必须至少阅读了其他ai个章节,才能够获取足够的智慧来读懂该章节。
每天,Zayin都会从头到尾开始阅读这本书。对于她还不能读懂的章节(由于限制)或是已经阅读过的章节,Zayin会在那天跳过它们。
现在,Zayin想要知道至少需要多少天才能阅读完所有的n个章节。


输入

第一行包含两个整数d, n,表示测试点编号和章节数。
第二行包含n个整数ai (0 ≤ ai<n),表示限制。

输出

输出一行包含一个整数,表示最少需要的天数。
如果Zayin无法阅读完所有的n个章节,输出−1。

样例输入 复制

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

样例输出 复制

2

提示

数据范围:

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

对于所有测试数据,保证1n5×105 ,0≤ai<n。

Subtask 1(10%):1≤n≤10,d=1。

Subtask 2(10%):1≤n≤500,d=2。

Subtask 3(20%):1≤n≤5000,3≤d≤4。

Subtask 4(20%):1≤n≤105,5≤d≤6。

Subtask 5(40%) :1≤n≤5×105,7≤d≤10。