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 to gain enough wisdom to understand this chapter.

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

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

Input

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

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

Output

Output a single integer representing the minimum number of days required.

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

Examples

Input 1

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

Output 1

2

Constraints

This problem uses subtask-based testing.

For all test data, it is guaranteed that $1 \le n \le 5 \times 10^5$ and $0 \le a_i < n$.

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