Problem Description

Zayin is a student who loves reading.

Recently, Zayin received a book with $n$ chapters. Each chapter $i$ has a requirement: she must have read at least $a_i$ other chapters before she can gain enough wisdom to understand that chapter.

Every day, Zayin starts reading the book from the beginning to the end. For chapters that she still cannot understand (due to the requirement) or chapters that she has already read, Zayin will skip them on that day.

Now, Zayin wants to know the minimum number of days needed to finish reading all $n$ chapters.

Input Format

The first line contains two integers $d, n$, representing the test point ID and the number of chapters.

The second line contains $n$ integers $a_i (0 \leq a_i < n)$, representing the requirements.

Output Format

Output one line containing one integer, representing the minimum number of days needed.

If Zayin cannot finish reading all $n$ chapters, output $-1$.

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

2

Hint

This problem uses bundled subtasks.

For all testdata, it is guaranteed that $1 \leq n \leq 5 \times 10^5$, $0 \leq a_i < n$.

• Subtask 1 (10%): $1 \leq n \leq 10$, $d = 1$.
• Subtask 2 (10%): $1 \leq n \leq 500$, $d = 2$.
• Subtask 3 (20%): $1 \leq n \leq 5000$, $3 \leq d \leq 4$.
• Subtask 4 (20%): $1 \leq n \leq 10^5$, $5 \leq d \leq 6$.
• Subtask 5 (40%): $1 \leq n \leq 5 \times 10^5$, $7 \leq d \leq 10$.

Translated by ChatGPT 5