Background

2024GDKOI pj day2

Description

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

最近，Zayin 收到了一本有 n 个章节的书，其中每个章节 i 都有一个限制：她必须至少阅读了其他 ai 个

章节，才能够获取足够的智慧来读懂该章节。

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

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

Format

Input

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

第二行包含 n 个整数 ai (0 ≤ ai < n)，表示限制。

Output

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

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

Samples

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

2

Limitation

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

对于所有测试数据，保证 1 ≤ n ≤ 5 × 10^5 , 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 ≤ 10^5 , 5 ≤ d ≤ 6。

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