Given a natural k and several numbers x_{1}, …, x_{n}, we want to find the smallest possible set of closed intervals of length k that cover those numbers. In other words, we must find a set of intervals {[y_{1}, y_{1} + k], …, [y_{m}, y_{m} + k]} such that
For instance, if k=10 and the x_{i}’s are 14, 19, 23 and 27, a possible solution is {[12, 22], [1.8, 2.8]}, since every x_{i} belongs to (at least) one of the two intervals, and it is not possible to cover the four numbers with a single interval.
Input
Input consists of several cases, each of which starts with k, followed by n, followed by n different numbers. All numbers in the input are integers. Assume 1 ≤ k, n ≤ 10^{5}.
Output
For every case, print the minimum number of closed intervals of length k that cover the given numbers.
Input
10 4 14 19 23 27 100 6 175 350 50 300 150 20 10 2 -25 -35
Output
2 3 1